#include <QApplication> // For mouse icon changing
#include <QtConcurrentRun> // For easy multi-threading
#include <QQueue>

#include "TaskCurve.h"
#include "TaskSheet.h"
#include "Scheduler.h"
#include "Relink.h"

#include "Synthesizer.h"
#include "GraphDissimilarity.h"

#include "kmeans1d.h"
#include "kmeans.h"
#include "kmedoid.h"

#include "SoftwareRenderer.h"

#include "TaskGroups.h"

#include "Scheduler.h"
#include "SchedulerWidget.h"

Q_DECLARE_METATYPE( QSet<int> ) // for tags

	Scheduler::Scheduler() : globalStart(0.0), globalEnd(1.0), timeStep( 1.0 / 100.0 ), overTime(0.0), isApplyChangesUI(false)
{
	rulerHeight = 25;

	originalActiveGraph = originalTargetGraph = NULL;
	activeGraph = targetGraph = NULL;
	slider = NULL;
	widget = NULL;
}

Scheduler::~Scheduler()
{
	qDeleteAll(allGraphs);
	allGraphs.clear();

	qDeleteAll(tasks);
	tasks.clear();

	if(widget) delete widget;
	if(slider) delete slider;

	delete originalActiveGraph;
	delete originalTargetGraph;

	delete activeGraph;
	delete targetGraph;
}

Scheduler::Scheduler( const Scheduler& other )
{
	// Properties
	rulerHeight = other.rulerHeight;
	isForceStop = other.isForceStop;
	property = other.property;
	isApplyChangesUI = other.isApplyChangesUI;

	// UI elements
	widget = NULL;
	slider = NULL;
	dock = NULL;

	// Execution parameters
	timeStep = other.timeStep;
	globalStart = other.globalStart;
	globalEnd = other.globalEnd;
	overTime = other.overTime;

	// Input
	setInputGraphs( other.originalActiveGraph, other.originalTargetGraph );
	superNodeCorr = other.superNodeCorr;
	activeGraph = NULL;
	targetGraph = NULL;

	this->generateTasks();
	this->schedule();
}

Scheduler * Scheduler::clone()
{
	return new Scheduler(*this);
}

void Scheduler::drawBackground( QPainter * painter, const QRectF & rect )
{
	QGraphicsScene::drawBackground(painter,rect);

	int y = rect.y();
	int screenBottom = y + rect.height();

	// Draw tracks
	for(int i = 0; i < (int)tasks.size() * 1.25; i++)
	{
		int y = i * 17;
		painter->fillRect(-10, y, 4000, 16, QColor(80,80,80));
	}

	// Draw current time indicator
	int ctime = slider->currentTime();
	painter->fillRect(ctime, 0, 1, screenBottom, QColor(0,0,0,128));

	// Draw tags for interesting topology changes
	{
		int tagWidth = 5;
		QSet<int> timeTags = property["timeTags"].value< QSet<int> >();

		foreach(int tagTime, timeTags)
		{
			painter->fillRect(tagTime - (0.5 * tagWidth), 0, tagWidth, screenBottom, QColor(100,100,100,128));
		}
	}
}

void Scheduler::drawForeground( QPainter * painter, const QRectF & rect )
{
	int x = rect.x();
	int y = rect.y();

	// Draw ruler
	int screenBottom = y + rect.height();
	painter->fillRect(x, screenBottom - rulerHeight, rect.width(), rulerHeight, QColor(64,64,64));

	// Draw yellow line
	int yellowLineHeight = 2;
	painter->fillRect(x, screenBottom - rulerHeight - yellowLineHeight, rect.width(), yellowLineHeight, Qt::yellow);

	// Draw text & ticks
	int totalTime = totalExecutionTime();
	int spacing = totalTime / 10;
	int timeEnd = 10;
	int minorTicks = 5;
	painter->setPen(Qt::gray);
	QFontMetrics fm(painter->font());

	if(overTime)
	{
		QRectF rect(0, 0, tasks.size() * tasks.front()->height, Task::DEFAULT_LENGTH);
		QPointF startPos = rect.topLeft() + QPointF(totalTime - overTime + rect.height(),0);

		painter->save();
		painter->translate(startPos);
		painter->rotate(90);
		painter->setBrush(QColor(255,255,0,20));
		painter->drawRect(rect);
		painter->drawText(rect, Qt::AlignCenter, "OVERTIME");
		painter->restore();
	}

	for(int i = 0; i <= timeEnd; i++)
	{
		double time = double(i) / timeEnd;

		int curX = i * spacing;

		QString tickText = QString("%1").arg(time);
		painter->drawText(curX - (fm.width(tickText) * 0.5), screenBottom - 14, tickText );

		// Major tick
		painter->drawLine(curX, screenBottom, curX, screenBottom - 10);

		if(i != timeEnd)
		{
			// Minor tick
			for(int j = 1; j < minorTicks; j++)
			{
				double delta = double(spacing) / minorTicks;
				int minorX = curX + (j * delta);
				painter->drawLine(minorX, screenBottom, minorX, screenBottom - 5);
			}
		}
	}

	slider->forceY(screenBottom - rulerHeight - 10);
	slider->setY(slider->myY);
	painter->translate(slider->pos());
	slider->paint(painter, 0, 0);
}

void Scheduler::setInputGraphs( Structure::Graph * source, Structure::Graph * target )
{
	originalActiveGraph = new Structure::Graph(*source);
	originalTargetGraph = new Structure::Graph(*target);
}

void Scheduler::generateTasks()
{
	tasks.clear();

	if( activeGraph ) delete activeGraph;
	if( targetGraph ) delete targetGraph;

	this->activeGraph = new Structure::Graph(*originalActiveGraph);
	this->targetGraph = new Structure::Graph(*originalTargetGraph);

	foreach(QString snodeID, superNodeCorr.keys())
	{
		QString tnodeID = superNodeCorr[snodeID];

		Task * task;

		if(activeGraph->getNode(snodeID)->type() == Structure::CURVE)
		{
			if (snodeID.contains("_null"))  // Grow
				task = new TaskCurve( activeGraph, targetGraph, Task::GROW, tasks.size() );
			else if (tnodeID.contains("_null")) // Shrink
				task = new TaskCurve( activeGraph, targetGraph, Task::SHRINK, tasks.size() );
			else
				task = new TaskCurve( activeGraph, targetGraph, Task::MORPH, tasks.size() );
		}

		if(activeGraph->getNode(snodeID)->type() == Structure::SHEET)
		{
			if (snodeID.contains("_null"))  // Grow
				task = new TaskSheet( activeGraph, targetGraph, Task::GROW, tasks.size() );
			else if (tnodeID.contains("_null")) // Shrink
				task = new TaskSheet( activeGraph, targetGraph, Task::SHRINK, tasks.size() );
			else
				task = new TaskSheet( activeGraph, targetGraph, Task::MORPH, tasks.size() );
		}

		task->setNode( snodeID );
		tasks.push_back( task );
	}
}

void Scheduler::schedule()
{
	Task *current, *prev = NULL;

	foreach(Task * task, tasks)
	{
		// Create
		current = task;

		// Placement
		if(prev) current->moveBy(prev->x() + prev->width,prev->y() + (prev->height));
		current->currentTime = current->x();
		current->start = current->x();

		// Add to scene
		this->addItem( current );

		prev = current;
	}

	this->startAllSameTime();

	// Order and group here:
	this->order();

	// Time-line slider
	if(!slider)
	{
		slider = new TimelineSlider;
		slider->reset();
		this->connect( slider, SIGNAL(timeChanged(int)), SLOT(timeChanged(int)), Qt::QueuedConnection );
		this->addItem( slider );
	}
}

void Scheduler::order()
{
	QMultiMap<Task::TaskType,Task*> tasksByType;

	foreach(Task * task, tasks)
		tasksByType.insert(task->type, task);

	int curStart = 0;

	// General layout
	for(int i = Task::SHRINK; i <= Task::GROW; i++)
	{
		QList<Task*> curTasks = tasksByType.values(Task::TaskType(i));

		if(!curTasks.size()) continue;

		int futureStart = curStart;

		// Sort tasks by priority
		curTasks = sortTasksByPriority( curTasks );

		if(i == Task::MORPH)
		{
			foreach(Task* t, curTasks){
				t->setStart(curStart);
				futureStart = qMax(futureStart, t->endTime());
				curStart = futureStart;
			}
		}
		else
		{
			curTasks = sortTasksAsLayers( curTasks, curStart );
			foreach(Task* t, curTasks) futureStart = qMax(futureStart, t->endTime());
		}

		// Group events in same group
		Structure::Graph * g = (i == Task::SHRINK) ? activeGraph : targetGraph;
		groupStart(g, curTasks, curStart, futureStart);		

		curStart = futureStart;
	}

	// Remove large empty spaces between tasks [inefficient?]
	this->trimTasks();

	// Add small spaces between tasks
	{
		int timeSpacing = (totalExecutionTime() * timeStep * 3) + 1;

		QVector<Task*> allTasks = tasksSortedByStart();

		int N = allTasks.size();
		for(int i = 0; i < N; i++)
		{
			Task * currTask = allTasks[i];

			QList<Task*> before, after;
			splitTasksStartTime(currTask->endTime() - 1, before, after);

			foreach(Task* t, after)
				t->setStart( t->start + timeSpacing );

			while(i < N-1 && allTasks[i+1]->start == currTask->start) i++;
		}
	}

	// To-do: Collect tasks together?
}

void Scheduler::trimTasks()
{
	int curTime = 0;
	forever{
		QList<Task*> before, after;
		splitTasksStartTime(curTime, before, after);

		if(after.empty()) break;

		if(!before.empty())
		{
			int end = endOf( before );
			int start = startOf( after );

			int delta = end - start;
			if(delta < 0) 
				slideTasksTime(after, delta);
		}
		curTime += 50;
	}
}

void Scheduler::groupStart( Structure::Graph * g, QList<Task*> curTasks, int curStart, int & futureStart )
{
	if(!curTasks.size()) return;

	int i = curTasks.front()->type;

	foreach(QVector<QString> group, g->groups)
	{
		QVector<Task*> tasksInGroup;
		QVector<QString> groupTarget;

		// Check which tasks are in a group
		foreach(Task * t, curTasks){
			Structure::Node * n = (i == Task::SHRINK) ? t->node() : t->targetNode();

			if(group.contains(n->id))
				tasksInGroup.push_back(t);
		}

		// Check grouping from target graph
		if(!tasksInGroup.isEmpty()){
			Structure::Graph * tg = (i == Task::SHRINK) ? tasksInGroup.front()->target : tasksInGroup.front()->active;
			groupTarget = tg->groupsOf( tasksInGroup.front()->node()->id ).front();

			if(!groupTarget.isEmpty()){
				foreach(Task * t, curTasks){
					Structure::Node * n = (i == Task::SHRINK) ? t->targetNode() : t->node();
					if(groupTarget.contains(n->id) && !tasksInGroup.contains(t))
						tasksInGroup.push_back(t);
				}
			}
		}

		curStart = futureStart;

		// Assign same start for them				
		foreach(Task * t, tasksInGroup){
			curStart = qMin(curStart, t->start);		
		}
		foreach(Task * t, tasksInGroup){
			t->setStart(curStart);
			futureStart = qMax(futureStart, t->endTime());

			t->property["grouped"] = true;
		}
	}
}

QList<Task*> Scheduler::sortTasksByPriority( QList<Task*> currentTasks )
{
	QList<Task*> sorted;

	// Sort by type: Sheets before curves
	QMap<Task*,int> curveTasks, sheetTasks;
	foreach(Task* t, currentTasks)
	{
		if(!t->node()) continue;

		if(t->node()->type() == Structure::CURVE) 
			curveTasks[t] = activeGraph->valence(t->node());
		if(t->node()->type() == Structure::SHEET) 
			sheetTasks[t] = activeGraph->valence(t->node());
	}

	// Sort by valence: Highly connected before individuals
	QList< QPair<int, Task*> > sortedCurve = sortQMapByValue(curveTasks);
	QList< QPair<int, Task*> > sortedSheet = sortQMapByValue(sheetTasks);

	// Combine: Curve[low] --> Curve[high] + Sheet[low] --> Sheet[heigh]
	for (int i = 0; i < (int)sortedCurve.size(); ++i) sorted.push_back( sortedCurve.at(i).second );
	for (int i = 0; i < (int)sortedSheet.size(); ++i) sorted.push_back( sortedSheet.at(i).second );

	// Reverse
	for(int k = 0; k < (sorted.size()/2); k++) sorted.swap(k,sorted.size()-(1+k));

	return sorted;
}

QList<Task*> Scheduler::sortTasksAsLayers( QList<Task*> currentTasks, int startTime )
{
	QList<Task*> sorted;

	QVector< QList<Task*> > groups = TaskGroups::split(currentTasks, activeGraph);

	int futureStart = -1;

	foreach(QList<Task*> group, groups)
	{
		TaskGroups::Graph g( group, activeGraph );

		QVector< QList<Task*> > layers = g.peel();

		if(currentTasks.front()->type == Task::SHRINK)
			layers = reversed(layers);

		foreach(QList<Task*> layer, layers)
		{
			foreach(Task* t, layer){
				t->setStart(startTime);
				futureStart = qMax(futureStart, t->endTime());
			}

			startTime = futureStart;

			sorted += layer;
		}
	}

	return sorted;
}

void Scheduler::reset()
{
	// Save assigned schedule
	QMap< QString,QPair<int,int> > curSchedule = getSchedule();

	// Clean previous outputs
	qDeleteAll(allGraphs);
	allGraphs.clear();

	// Clean old tasks
	foreach(Task * task, tasks)	this->removeItem(task);
	tasks.clear();

	// Remove any tags
	property.remove("timeTags");

	/// Reload graphs:	
	this->generateTasks();
	this->schedule();

	// Reassign schedule
	this->setSchedule( curSchedule );
	emit( progressChanged(0) );
	emit( hasReset() );
}

void Scheduler::executeAll()
{
	int totalTime = totalExecutionTime();
	QVector<Task*> allTasks = tasksSortedByStart();

	if( isApplyChangesUI ) qApp->setOverrideCursor(Qt::WaitCursor);

	// pre-execute
	{
		property["progressDone"] = false;
		isForceStop = false;

		emit( progressStarted() );

		// Tag interesting topology changes
		{
			property.remove("timeTags");

			QSet<int> tags;
			foreach(Task * task, allTasks){
				int time = task->start + (0.5 * task->length);
				tags.insert( time );
			}

			property["timeTags"].setValue( tags );
		}
	}

	Relink linker(this);

	// Initial setup
	{
		// Process null nodes
		foreach(Structure::Node * snode, activeGraph->nodes)
		{
			QString sid = snode->id;
			if (!sid.contains("_null")) continue;

			// Zero the geometry for null nodes
			snode->setControlPoints( Array1D_Vector3(snode->numCtrlPnts(), Vector3(0,0,0)) );
			snode->property["zeroGeometry"] = true;

			bool isPartOfCutGroup = activeGraph->isInCutGroup(sid);
			bool isCutNode = activeGraph->isCutNode(sid);

			if( !isCutNode && !isPartOfCutGroup )
			{
				// Make sure it is "effectively" linked on only one existing node
				QMap<Link *,int> existValence;
				foreach(Link * edge, activeGraph->getEdges(sid)){
					QString otherID = edge->otherNode(sid)->id;
					if(otherID.contains("_null")) continue;
					existValence[edge] = activeGraph->valence(activeGraph->getNode(otherID));
				}

				// Ignore if connects to one existing
				if(existValence.size() < 2) 
					continue;

				// Pick existing node with most valence
				QList< QPair<int, Link *> > sorted = sortQMapByValue(existValence);
				Link * linkKeep = sorted.back().second;

				// Replace all edges of null into the kept edge
				foreach(Link * edge, activeGraph->getEdges(sid))
				{
					if(edge == linkKeep) continue;

					// Keep track of original edge info
					QString oldNode = edge->otherNode(sid)->id;
					edge->pushState();
					edge->replace(oldNode, linkKeep->otherNode(sid), linkKeep->getCoordOther(sid));
				}

				snode->property["edgesModified"] = true;
			}
		}

		// Relink once to place null nodes at initial positions:
		QVector<QString> aTs; 
		foreach (Task* task, allTasks) {if ( task->type != Task::GROW)	aTs << task->nodeID;}
		if (aTs.isEmpty()) aTs << allTasks.front()->nodeID;
		activeGraph->property["activeTasks"].setValue( aTs );

		linker.execute();

		// Debug: 
		//allGraphs.push_back( new Structure::Graph( *activeGraph ) );
	}

	// Execute all tasks
	for(double globalTime = globalStart; globalTime <= (globalEnd + timeStep); globalTime += timeStep)
	{
		QElapsedTimer timer; timer.start();

		// DEBUG - per pass
		activeGraph->clearDebug();

		// active tasks
		QVector<QString> aTs = activeTasks(globalTime * totalTime);
		activeGraph->property["activeTasks"].setValue( aTs );
		activeGraph->property["t"] = qMin(1.0, globalTime);

		// For visualization
		activeGraph->setPropertyAll("isActive", false);

		// Blend deltas
		blendDeltas( globalTime, timeStep );

		/// Prepare and execute current tasks
		for(int i = 0; i < (int)allTasks.size(); i++)
		{
			Task * task = allTasks[i];
			double localTime = task->localT( globalTime * totalTime );
			if( localTime < 0 || task->isDone ) continue;

			// Prepare task for grow, shrink, morph
			task->prepare();

			// Execute current task at current time
			task->execute( localTime );

			// For visualization
			if(localTime >= 0.0 && localTime < 1.0) task->node()->property["isActive"] = true;
		}

		/// Geometry morphing
		foreach(Task * task, allTasks)
		{
			double localTime = task->localT( globalTime * totalTime );
			if( localTime < 0 ) continue;
			task->geometryMorph( localTime );
		}

		/// Apply relinking
		linker.execute();

		// Output current active graph:
		activeGraph->property["graphIndex"] = allGraphs.size();
		allGraphs.push_back(  new Structure::Graph( *activeGraph )  );

		// DEBUG:
		activeGraph->clearDebug();

		// UI - progress visual indicator:
		int percent = globalTime * 100;
		property["progress"] = percent;
		emit( progressChanged(percent) );

		if( isForceStop ) break;
	}

	finalize();

	property["progressDone"] = true;

	if( isApplyChangesUI ) 
	{
		slider->enable();

		qApp->restoreOverrideCursor();
		QCursor::setPos(QCursor::pos());
	}

	emit( progressDone() );
}

void Scheduler::finalize()
{
	double sumDistortion = 0;

	double distThreshold = activeGraph->bbox().diagonal().norm() * 0.1;

	foreach(Node * n, activeGraph->nodes){
		if(n->property["shrunk"].toBool()) continue;

		Node * tn = targetGraph->getNode( n->property["correspond"].toString() );
		double curDistortion = n->distortion( tn );
		sumDistortion += curDistortion;
	}

	// Make sure we exactly get the target, no constraints here
	if(sumDistortion > distThreshold){
		double finalizeDuration = double(Task::DEFAULT_LENGTH) / totalExecutionTime();

		// Reassign 't' values for generated graphs
		double stretch = (totalExecutionTime() - overTime) / totalExecutionTime();
		for(int i = 0; i < (int)allGraphs.size(); i++)
			allGraphs[i]->property["t"] = qMin(1.0, stretch * (allGraphs[i]->property["t"].toDouble()));

		QMap<Node*, Array1D_Vector3> curGeometry;
		foreach(Node * n, activeGraph->nodes)
			curGeometry[n] = n->controlPoints();

		int steps = int(finalizeDuration / timeStep);

		for(int u = 0; u <= steps; u++){
			double t = double(u) / steps;

			// Morph nodes
			foreach(Node * n, activeGraph->nodes){
				Node * tn = targetGraph->getNode( n->property["correspond"].toString() );
				Array1D_Vector3 finalGeometry = tn->controlPoints();
				Array1D_Vector3 newGeometry;

				for(int i = 0; i < (int) finalGeometry.size(); i++)
					newGeometry.push_back( AlphaBlend(t, curGeometry[n][i], Vector3(finalGeometry[i])) );

				n->setControlPoints( newGeometry );
			}

			allGraphs.push_back(  new Structure::Graph( *activeGraph )  );
		}

		overTime = Task::DEFAULT_LENGTH;

		// Move last tag to overtime
		QSet<int> modfiedTags = property["timeTags"].value< QSet<int> >();
		int lastVal = modfiedTags.values().back();
		modfiedTags.remove(lastVal);
		modfiedTags.insert(totalExecutionTime() - (0.5 * Task::DEFAULT_LENGTH));
		property["timeTags"].setValue(modfiedTags);
	}
}

void Scheduler::drawDebug()
{
	foreach(Task * t, tasks)
	{
		t->drawDebug();
	}
}

int Scheduler::totalExecutionTime()
{
	int endTime = 0;

	foreach(Task * t, tasks)
		endTime = qMax(endTime, t->endTime());

	return endTime + overTime;
}

void Scheduler::timeChanged( int newTime )
{
	if(!allGraphs.size()) return;

	int idx = allGraphs.size() * (double(newTime) / totalExecutionTime());

	idx = qRanged(0, idx, allGraphs.size() - 1);
	allGraphs[idx]->property["graphIndex"] = idx;

	emit( activeGraphChanged(allGraphs[idx]) );
}

void Scheduler::doBlend()
{
	foreach(Task * t, tasks) t->setSelected(false);

	// If we are re-executing, we need to reset everything
	if(allGraphs.size())
		reset();

	/// Execute the tasks on a new thread
	QtConcurrent::run( this, &Scheduler::executeAll ); // scheduler->executeAll();
}

QVector<Task*> Scheduler::tasksSortedByStart()
{
	QMap<Task*,int> tasksMap;
	typedef QPair<int, Task*> IntTaskPair;
	foreach(Task* t, tasks) tasksMap[t] = t->start;
	QList< IntTaskPair > sortedTasksList = sortQMapByValue<Task*,int>( tasksMap );
	QVector< Task* > sortedTasks; 
	foreach( IntTaskPair p, sortedTasksList ) sortedTasks.push_back(p.second);
	return sortedTasks;
}

void Scheduler::stopExecution()
{
	isForceStop = true;
}

void Scheduler::startAllSameTime()
{
	if(selectedItems().isEmpty())
	{
		foreach(Task * t, tasks)
			t->setX(0);
	}
	else
	{
		// Get minimum start
		int minStart = INT_MAX;
		foreach(Task * t, tasks){
			if(t->isSelected())
				minStart = qMin( minStart, t->start );
		}

		foreach(Task * t, tasks){
			if(t->isSelected())
				t->setX( minStart );
		}
	}
}

void Scheduler::startDiffTime()
{
	if(selectedItems().isEmpty())
	{
		for(int i = 0; i < (int)tasks.size(); i++){
			int startTime = 0;
			if(i > 0) startTime = tasks[i - 1]->endTime();
			tasks[i]->setX( startTime );
		}
	}
	else
	{
		int startTime = -1;
		foreach(Task * t, tasks){
			if(t->isSelected())
			{
				if(startTime < 0) startTime = t->start;
				t->setX( startTime );
				startTime += t->length;
			}
		}
	}
}

void Scheduler::prepareSynthesis()
{

}

Task * Scheduler::getTaskFromNodeID( QString nodeID )
{
	foreach(Task * t, tasks) if(t->node()->id == nodeID) return t;
	return NULL;
}

QVector<QString> Scheduler::activeTasks( double globalTime )
{
	QVector<QString> aTs;

	for(int i = 0; i < (int)tasks.size(); i++)
	{
		Task * task = tasks[i];
		double localTime = task->localT( globalTime );

		bool isActive = task->isActive( localTime );

		// Consider future growing cut nodes as active
		bool isUngrownCut = (!task->isDone) && (task->type == Task::GROW) && (task->node()->property.contains("isCutGroup"));

		// HH - Why?
		// Consider dead links as active tasks
		//bool isDeadLink = task->isDone && (task->type == Task::SHRINK);
		bool isDeadLink = false;

		if ( isActive || isUngrownCut || isDeadLink )
		{
			aTs.push_back( task->node()->id );
		}
	}

	return aTs;
}

void Scheduler::splitTasksStartTime( int startTime, QList<Task*> & before, QList<Task*> & after )
{
	foreach(Task * t, tasks){
		if(t->start < startTime)
			before.push_back(t);
		else
			after.push_back(t);
	}
}

void Scheduler::slideTasksTime( QList<Task*> list_tasks, int delta )
{
	foreach(Task * t, list_tasks){
		t->setStart( t->start + delta );
	}
}

int Scheduler::startOf( QList<Task*> list_tasks )
{
	int start = INT_MAX;
	foreach(Task * t, list_tasks) start = qMin(start, t->start);
	return start;
}

int Scheduler::endOf( QList<Task*> list_tasks )
{
	int end = -INT_MAX;
	foreach(Task * t, list_tasks) end = qMax(end, t->endTime());
	return end;
}

void Scheduler::addMorphTask( QString nodeID )
{
	Task * prev = tasks.back();

	Task * task;

	if(activeGraph->getNode(nodeID)->type() == Structure::CURVE)
		task = new TaskCurve( activeGraph, targetGraph, Task::MORPH, tasks.size() );

	if(activeGraph->getNode(nodeID)->type() == Structure::SHEET)
		task = new TaskSheet( activeGraph, targetGraph, Task::MORPH, tasks.size() );

	task->setNode( nodeID );
	tasks.push_back( task );

	// Placement
	task->moveBy(prev->x() + prev->width,prev->y() + (prev->height));
	task->currentTime = task->x();
	task->start = task->x();

	// Add to scene
	this->addItem( task );
}

void Scheduler::blendDeltas( double globalTime, double timeStep )
{
	if (globalTime >= 1.0) return;

	Q_UNUSED( timeStep );
	//double alpha = timeStep / (1 - globalTime);

	foreach(Structure::Link* l, activeGraph->edges)
	{
		Structure::Link* tl = targetGraph->getEdge(l->property["correspond"].toInt());
		if (!tl) continue;

		//Alpha value:
		double alpha = 0;
		{
			Task * sTask1 = l->n1->property["task"].value<Task*>();
			Task * sTask2 = l->n2->property["task"].value<Task*>();

			if(sTask1->isDone && sTask2->isDone) 
			{
				alpha = 1.0;
			}
			else if( sTask1->isDone )
			{
				alpha = sTask2->property["t"].toDouble();
			}
			else
			{
				alpha = sTask1->property["t"].toDouble();
			}
		}

		Vector3d sDelta = l->delta();
		Vector3d tDelta = tl->property["delta"].value<Vector3d>();

		// flip tDelta if is not consistent with sDeltas
		Node *sn1 = l->n1;

		/// Prevent large gaps
		{
			alpha = qMax(alpha, activeGraph->property["t"].toDouble() * 0.8 );
		}

		Vector3d blendedDelta = AlphaBlend(alpha, sDelta, tDelta);

		/// Prevent large gaps
		{
			double gapLimiter = (0.2) * (1.0 - pow((alpha-0.5)*2, 2));
			blendedDelta = blendedDelta * (1.0 - gapLimiter);
		}

		l->property["blendedDelta"].setValue( blendedDelta );

		// Visualization
		activeGraph->vs3.addVector(l->position(sn1->id), blendedDelta);
		//activeGraph->vs.addVector(l->position(sn1->id), tDelta);
	}
}

void Scheduler::setGDResolution( double r)
{
	DIST_RESOLUTION = r;
}

void Scheduler::setTimeStep( double dt )
{
	timeStep = dt;
}

void Scheduler::loadSchedule(QString filename)
{
	QFile file(filename);
	if (!file.open(QIODevice::ReadOnly | QIODevice::Text)) return;
	QFileInfo fileInfo(file.fileName());

	QTextStream in(&file);

	int N = 0; 
	QString nodeID;
	int start = 0, length = 0;

	in >> N; if(N != tasks.size()) { qDebug() << "Invalid schedule!"; return; }

	for(int i = 0; i < N; i++)
	{
		in >> nodeID >> start >> length;
		Task * t = getTaskFromNodeID( nodeID );

		if( t )
		{
			t->setStart( start );
			t->setLength( length );
		}
	}

	file.close();
}

void Scheduler::saveSchedule(QString filename)
{
	QFile file(filename);
	if (!file.open(QIODevice::WriteOnly | QIODevice::Text)) return;
	QFileInfo fileInfo(file.fileName());

	QTextStream out(&file);
	out << tasks.size() << "\n";
	foreach(Task * t, tasks)	out << t->nodeID << " " << t->start << " " << t->length << "\n";
	file.close();
}

void Scheduler::saveSchedule(QString filename, ScheduleType s)
{
	QFile file(filename);
	if (!file.open(QIODevice::WriteOnly | QIODevice::Text)) return;
	QFileInfo fileInfo(file.fileName());

	QTextStream out(&file);
	out << s.size() << "\n";
	foreach(QString nid, s.keys())	out << nid << " " << s[nid].first << " " << s[nid].second << "\n";
	file.close();
}

ScheduleType Scheduler::getSchedule()
{
	ScheduleType result;
	foreach(Task * t, tasks) result[t->nodeID] = qMakePair( t->start, t->length );
	return result;
}

ScheduleType Scheduler::reversedSchedule(const ScheduleType & fromSchedule)
{
	ScheduleType result;

	QMap< int, QVector<QString> > startTask;

	foreach(QString task, fromSchedule.keys())
		startTask[fromSchedule[task].first].push_back(task);

	// These keys are sorted in increasing order
	QVector<int> originalTimes = startTask.keys().toVector();

	// Shuffle them
	QVector<int> startTimes = originalTimes;
	std::reverse(startTimes.begin(), startTimes.end());

	for(int i = 0; i < (int)startTimes.size(); i++)
	{
		int oldStart = originalTimes[i];
		int newStart = startTimes[i];

		QVector<QString> curTasks = startTask[oldStart];

		foreach(QString t, curTasks)
		{
			result[t] = qMakePair(newStart, fromSchedule[t].second);
		}
	}

	return result;
}

void Scheduler::setSchedule( ScheduleType fromSchedule )
{
	Task * t = NULL;
	foreach(QString nodeID, fromSchedule.keys())
	{
		if(t = getTaskFromNodeID(nodeID))
		{
			t->setStart(fromSchedule[nodeID].first);
			t->setLength(fromSchedule[nodeID].second);
		}
	}
}

void Scheduler::defaultSchedule()
{
	this->startDiffTime();
	this->order();
}

void Scheduler::mouseReleaseEvent( QGraphicsSceneMouseEvent * event )
{
	emit( updateExternalViewer() );
	QGraphicsScene::mouseReleaseEvent(event);
}

void Scheduler::mousePressEvent( QGraphicsSceneMouseEvent * event )
{
	property["mouseFirstPress"] = true;

	QGraphicsScene::mousePressEvent(event);

	// Reset on changes to schedule
	if(allGraphs.size()){
		foreach(Task* t, tasks){
			if(t->isSelected()){
				this->reset();
				emitUpdateExternalViewer();
			}
		}
	}
}

void Scheduler::mouseMoveEvent( QGraphicsSceneMouseEvent * event )
{
	if(property["mouseFirstPress"].toBool()){
		property["mouseFirstPress"] = false;
		emitUpdateExternalViewer();
	}

	QGraphicsScene::mouseMoveEvent(event);
}

void Scheduler::emitUpdateExternalViewer()
{
	emit( updateExternalViewer() );
}

void Scheduler::emitProgressStarted()
{
	emit( progressStarted() );
}

void Scheduler::emitProgressChanged( int val )
{
	emit( progressChanged(val) );
}

void Scheduler::emitProgressedDone()
{
	emit( progressDone() );
}

void Scheduler::shuffleSchedule()
{
	if(allGraphs.size()) reset();

	QMap< int, QVector<Task*> > startTask;

	foreach(Task * t, this->tasks)
		startTask[t->start].push_back(t);

	// These keys are sorted in increasing order
	QVector<int> originalTimes = startTask.keys().toVector();

	// Shuffle them
	QVector<int> startTimes = originalTimes;
	std::random_shuffle(startTimes.begin(), startTimes.end());

	for(int i = 0; i < (int)startTimes.size(); i++)
	{
		int oldStart = originalTimes[i];
		int newStart = startTimes[i];

		QVector<Task*> curTasks = startTask[oldStart];

		foreach(Task * t, curTasks)
		{
			t->setStart( newStart );
		}
	}
}

QVector<ScheduleType> Scheduler::manyRandomSchedules(int N)
{
	QVector<ScheduleType> schedules;

	if(allGraphs.size()) reset();
	QMap< int, QVector<Task*> > startTask;
	foreach(Task * t, this->tasks)	startTask[t->start].push_back(t);
	QVector<int> originalTimes = startTask.keys().toVector();
	QVector<int> startTimes = originalTimes;

	// Add the default scheduling as first possibility
	schedules.push_back( getSchedule() );

	// Add the reverse of the default scheduling
	if(N > 1) schedules.push_back( Scheduler::reversedSchedule(schedules.front()) );

	for(int itr = 2; schedules.size() < N; itr++)
	{
		std::random_shuffle(startTimes.begin(), startTimes.end());

		ScheduleType s;

		for(int i = 0; i < (int)startTimes.size(); i++)
		{
			int oldStart = originalTimes[i];
			int newStart = startTimes[i];

			QVector<Task*> curTasks = startTask[oldStart];

			foreach(Task * t, curTasks)
				s[ t->nodeID ] = qMakePair(newStart, t->length);
		}

		schedules.push_back( s );
	}

	return schedules;
}

QVector<ScheduleType> Scheduler::allSchedules()
{
	QVector<ScheduleType> schedules;

	if(allGraphs.size()) reset();
	QMap< int, QVector<Task*> > startTask;
	foreach(Task * t, this->tasks)	startTask[t->start].push_back(t);
	QVector<int> originalTimes = startTask.keys().toVector();
	QVector<int> startTimes = originalTimes;

	do {
		ScheduleType s;

		for(int i = 0; i < (int)startTimes.size(); i++){
			int oldStart = originalTimes[i];
			int newStart = startTimes[i];
			QVector<Task*> curTasks = startTask[oldStart];

			foreach(Task * t, curTasks)
				s[ t->nodeID ] = qMakePair(newStart, t->length);
		}

		schedules.push_back( s );
	} while( std::next_permutation(startTimes.begin(), startTimes.end()) );

	return schedules;
}

QVector<Structure::Graph*> Scheduler::interestingInBetweens(int N)
{
	QVector<Structure::Graph*> result;
	if(!allGraphs.size()) return result;

	QSet<int> tags = property["timeTags"].value< QSet<int> >();
	int totalTime = totalExecutionTime();

	QVector<double> times;

	foreach(int tag, tags){
		double t = double(tag) / totalTime;
		times.push_back(t);
	}
	qSort(times);

	if(times.size() < 3){
		times.clear();
		times.push_back(0.1);
		times.push_back(0.9);
	}

	// Missing some more samples
	while(times.size() < N)
	{
		QMap<double, int> intervals;
		for(int i = 0; i + 1 < times.size(); i++)
			intervals[times[i+1] - times[i]] = i;

		int selected = intervals[intervals.keys().back()];
		double length = times[ selected + 1 ] - times[ selected ];
		double midTime = (length * 0.5) + times[selected];

		times.push_back(midTime);
		qSort(times);
	}

	// Having a lot more samples
	while(times.size() > N)
	{
		QMap<double, int> intervals;

		// Note we start from '1'
		for(int i = 1; i + 1 < times.size() - 1; i++)
			intervals[times[i+1] - times[i]] = i;

		int selected = intervals[intervals.keys().front()];
		times.remove( selected );
	}

	foreach(double t, times)
		result.push_back( allGraphs[ t * (allGraphs.size() - 1) ] );

	return result;
}

QVector<Structure::Graph*> Scheduler::topoVaryingInBetweens(int N, bool isVisualize)
{
	QVector<Structure::Graph*> samples;
	if(allGraphs.size() < 2) return samples;

	QSharedPointer<Structure::Graph> firstInstance = QSharedPointer<Structure::Graph>( Structure::Graph::actualGraph( allGraphs.front() ) );
	QSharedPointer<Structure::Graph> lastInstance = QSharedPointer<Structure::Graph>( Structure::Graph::actualGraph( allGraphs.back() ) );

	if(!firstInstance->nodes.size() || !lastInstance->nodes.size()) return interestingInBetweens(N);

	/// Topological
	GraphDissimilarity gd( firstInstance.data() );

	// compare against these
	gd.addGraph( firstInstance.data() );
	gd.addGraph( lastInstance.data() );

	/// Geometric
	int thumbWidth = 40;
	MatrixXd V = MatrixXd::Zero( allGraphs.size(), thumbWidth * thumbWidth);

	QString fixedPart = "";
	Vector3 fixedCenter(0,0,0);

	for(int i = 0; i < allGraphs.size(); i++)
	{
		Structure::Graph * g = Structure::Graph::actualGraph(allGraphs[i]);

		// Topological dissimilarity
		gd.addGraph( g );

		// Geometric dissimilarity
		{
			QVector<Vector3> cpnts;

			if( !fixedPart.isEmpty() )
			{
				Node * fixed = g->getNode(fixedPart);

				// If we lost the fixed part, find another..
				if( !fixed ){
					foreach(Node * n, g->nodes){
						if(n->property["fixedSize"].toBool()){
							fixedPart = n->id;
							fixedCenter = n->bbox().center();
							break;
						}
					}
				}
				else
				{
					Vector3 delta = fixedCenter - fixed->bbox().center();
					g->translate(delta, true);
				}
			}
			else
			{
				foreach(Node * n, g->nodes){
					if(n->property["fixedSize"].toBool()){
						fixedPart = n->id;
						fixedCenter = n->bbox().center();
						break;
					}
				}
			}

			foreach(Node * n, g->nodes) foreach(Vector3 p, n->controlPoints()) cpnts << p;

			// Normalize and fit
			{
				Vector3 mean(0,0,0);
				foreach(Vector3 p, cpnts) mean += p;
				mean /= cpnts.size();
				double scale = -1.0;
				foreach(Vector3 p, cpnts) scale = qMax(scale, (p-mean).norm());
				for(int pi = 0; pi < cpnts.size(); pi++) cpnts[pi] = ((cpnts[pi] - mean) / scale);
			}

			MatrixXd thumbnail = SoftwareRenderer::render(cpnts, thumbWidth, thumbWidth, 2, Vector3(0,0,0));

			//if( isVisualize ) SoftwareRenderer::matrixToImage(thumbnail).save(QString("skeleton_%1.png").arg(i));
			
			// Fill to a vector
			for(int d = 0; d < thumbWidth * thumbWidth; d++) 
			{
				V(i,d) = thumbnail(d);
			}
		}

		delete g;
	}

	QVector< QPair<double,double> > dissimilarVals = gd.computeDissimilarPairs(2);

	// Add topology measure
	for(int i = 0; i < allGraphs.size(); i++)
	{
		if(i < allGraphs.size() * 0.5)
			V.row(i) *= (1 + dissimilarVals[i].first) * 0.5;
		else
			V.row(i) *= (1 + dissimilarVals[i].second) * 0.5;
	}

	QVector<int> classes(allGraphs.size());

	kmeansFast::Clusters clusters = kmeansFast::kmeans(V, N);

	for(int i = 0; i < allGraphs.size(); i++)
		classes[i] = clusters.cluster[i];

	QMap< int, QVector<int> > clusterMap;
	for(int i = 0; i < (int)clusters.cluster.size(); i++){
		clusterMap[ classes[i] ].push_back(i);
	}

	// Get midpoint for each cluster
	QSet<int> midPoints;
	int totalTime = totalExecutionTime();

	foreach(int c, clusterMap.keys()) 
	{
		QVector<int> elements = clusterMap[c];
		qSort(elements);

		// Bias with respect to active tasks status
		QMap<int, double> graphStatus;
		foreach(int e, elements)
		{
			double status = 0;
			QVector<QString> active = allGraphs[e]->property["activeTasks"].value< QVector<QString> >();
			if(active.size()) status = allGraphs[e]->getNode(active.front())->property["t"].toDouble();
			
			//status = 1 - (std::abs(status - 0.5) * 2.0); // Favor end points: [0, 0.5, 1] => [1, 0, 1]
			//status = qMin(std::abs(0.25 - status), std::abs(0.75 - status)); // Favor 0.25 and 0.75 points
			status = std::abs(0.75 - status); // Favor 0.75

			graphStatus[e] = status;
		}

		int idx = sortQMapByValue(graphStatus).front().second;

		int time = allGraphs[idx]->property["t"].toDouble() * totalTime;
		
		midPoints.insert( time );
	}

	property["timeTags"].setValue( midPoints );

	samples = interestingInBetweens(N);

	// DEBUG:
	if( isVisualize )
	{
		QVector<int> chosenOnes;

		foreach(Structure::Graph * g, samples){
			chosenOnes.push_back( g->property["graphIndex"].toInt() );
		}

		QImage visualization(1000, 500, QImage::Format_RGB32);
		QPainter painter(&visualization);
		painter.setRenderHint(QPainter::Antialiasing);
		painter.setRenderHint(QPainter::HighQualityAntialiasing);
		painter.fillRect(visualization.rect(), Qt::white);
		painter.translate(visualization.width() * 0.05,visualization.height() * 0.05);
		painter.scale(0.9,0.9);

		QPainterPath path;

		QVector<QColor> randColors;
		for(int i = 0; i < N; i++){
			randColors.push_back(qRandomColor2());
			randColors[i].setAlphaF(0.8);
		}

		for(int i = 0; i < allGraphs.size(); i++)
		{
			double val = 1.0;
			
			if(i < allGraphs.size() * 0.5)
				val = dissimilarVals[i].first;
			else
				val = dissimilarVals[i].second;

			int x = (double(i) / (allGraphs.size() - 1)) * visualization.width();
			int y = val * visualization.height();

			// invert y-axis
			y = visualization.height() - y;

			// Topology
			if(i == 0) path.moveTo(x,y);
			else path.lineTo(x,y);

			painter.setBrush(randColors[ classes[i] ]);
			painter.drawEllipse(QPoint(x,y),3,3);
		}

		for(int j = 0; j < chosenOnes.size(); j++)
		{
			int i = chosenOnes[j];

			double val = 0.5;

			int x = (double(i) / (allGraphs.size() - 1)) * visualization.width();
			int y = val * visualization.height();

			// invert y-axis
			y = visualization.height() - y;

			painter.setBrush(randColors[ classes[i] ]);
			painter.drawEllipse(QPoint(x,y),10,10);

			painter.drawImage( x, y, SoftwareRenderer::matrixToImage( SoftwareRenderer::vectorToMatrix(V.row(i), thumbWidth, thumbWidth) ) );
		}

		// Topology
		painter.setPen(QColor::fromRgbF(0.5,0.5,0.5,0.8));
		painter.setBrush(Qt::NoBrush);
		painter.drawPath(path);

		visualization.save("vis.png");
	}

	return samples;
}