#include <vector>
#include <set>
#include <stdio.h>
#include <stdlib.h>

// the mutable definition is because we want to modify the set iterator directly
// I don't want to remove and insert as the position in sorted seq is not changed.
struct FrameIndexRenderMinute 
{
		int index;
mutable	int minute;
};


struct FrameIndexRenderMinuteCompByMinute 
{
	bool operator()(const FrameIndexRenderMinute& left, const FrameIndexRenderMinute& right) const
	{
		if (left.minute != right.minute)
		{
			return left.minute < right.minute;
		}
		else
		{
			return left.index < right.index;
		}
    }
};

struct FrameIndexRenderMinuteCompByIndex
{
	bool operator()(const FrameIndexRenderMinute& left, const FrameIndexRenderMinute& right) const
	{
		return left.index < right.index;
	}
};

// this set sorted by render minute
typedef std::set<FrameIndexRenderMinute, FrameIndexRenderMinuteCompByMinute> RenderJobSet;

// this set sorted by frame index
typedef std::set<FrameIndexRenderMinute, FrameIndexRenderMinuteCompByIndex> RenderJobSequenceSet;

typedef std::vector<FrameIndexRenderMinute> RenderJobVector;

typedef std::vector<RenderJobVector> RenderJobVectorVector; // the slot represents hourly jobs assignment

class RenderJobDispatch
{

public:

	void applyFinishedJobSet(RenderJobSet& renderJobSet, RenderJobVector& finishedJobVector)
	{
		// to do, remove finished job set from renderJobSet
                // also adjust job's render minute by the distance relative to finished job frame index
		int i;
		RenderJobSequenceSet renderSeqSet;
		RenderJobSequenceSet finishedSeqSet;
		// we create two set sorted by frame index
		for (i = 0; i < finishedJobVector.size(); i ++)
		{
		    finishedSeqSet.insert(finishedJobVector[i]);
		}
		
		for (RenderJobSet::iterator jobit = renderJobSet.begin(); jobit != renderJobSet.end(); jobit ++)
		{
		    renderSeqSet.insert(*jobit);
		}
		// now we remove the finished jobs
		for (i = 0; i < finishedJobVector.size(); i ++)
		{
		    //srcSeqSet.insert(finishedJobVector[i]);
		    renderSeqSet.erase(finishedJobVector[i]);
		}
		
		// clear it now, so we insert new updated jobs

		renderJobSet.clear();

		// we now need to adjust remain jobs' estimated render minute according to finished render minute
		// this is done by the average according to its frame index
		for (RenderJobSequenceSet::iterator it = renderSeqSet.begin(); it != renderSeqSet.end(); it ++)
		{
		    RenderJobSequenceSet::iterator loIt, upIt;
		    loIt = finishedSeqSet.lower_bound(*it);
		    upIt = finishedSeqSet.upper_bound(*it);
		    // get average render time relative to how close it is to up/lo bound
		    int loDistance, upDistance;
		    if (loIt == finishedSeqSet.end())
		    {
				loDistance = 0;
		    }
		    else
		    {
				loDistance = it->index - loIt->index;
		    }
            if (upIt == finishedSeqSet.end())
		    {
				upDistance = 0;
		    }
		    else
		    {
				upDistance = upIt->index - it->index;
		    }
		    FrameIndexRenderMinute node;
			int totalDistance = loDistance + upDistance;
			int newMinute;  
		    if (totalDistance != 0)
		    {
		        newMinute = (loIt->minute*loDistance + upIt->minute*upDistance)/totalDistance;
				
		        //it->minute = newMinute;
				//renderJobSet.begin()->minute = 0;
		    }
			else
			{
				newMinute = it->minute;
			}

			node.minute = newMinute;
			node.index = it->index;
			renderJobSet.insert(node);
		}		 
	}
private:
	/*
	int findMaxFitSlot(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
	{		
		if (jobSubSet.empty())
		{
			// no need to update renderJobSlot
		    return nLeftMinute;
		}
		int nMinLeftMinute;
		nMinLeftMinute = nLeftMinute;
		
		// and we know it is not empty
		RenderJobSet::iterator theFirst = jobSubSet.begin();

		// initialize the parameter
		int nNextLeftMinute = nLeftMinute - theFirst->minute;

		if (nNextLeftMinute < 0)
		{
		   return nLeftMinute;
		}
		renderJobVector.push_back(*theFirst);

		RenderJobVector tempJobVector, minJobVector;
		// copy the original result and add our first job at back
		
		minJobVector.assign(renderJobVector.begin(), renderJobVector.end());
		//tempJobVector.push_back(*theFirst);

		RenderJobSet nextRenderJobSet;

		// we can do this because jobSubSet is not empty 
		theFirst ++;
		RenderJobSet::iterator it;
		for (it = theFirst; it != jobSubSet.end(); ++ it)
		{
			nextRenderJobSet.insert(*it);
		}
		
		// next we iterate and try to find the minLeftMinute recursively 
		for (it = theFirst; it != jobSubSet.end(); it ++)
		{
		    // push stack		    
			tempJobVector.assign(renderJobVector.begin(), renderJobVector.end());
		    int nTempLeftMinute = findMaxFitSlot(nextRenderJobSet, nNextLeftMinute, tempJobVector);
			    
		    if (nTempLeftMinute >= 0 && nTempLeftMinute < nMinLeftMinute)
		    {
				nMinLeftMinute = nTempLeftMinute;
				minJobVector.assign(tempJobVector.begin(), tempJobVector.end());
		    }
		    // remove stack
		    //renderJobVector.pop_back();
		}
		// this is what we find, or possible nothing changed
		renderJobVector.assign(minJobVector.begin(), minJobVector.end());		
      	return nMinLeftMinute;
	}
*/


	int findMaxFitSlot(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
	{		
		return findMaxFitslotByGreedy(jobSubSet, nLeftMinute, renderJobVector);
	}


	int findMaxFitslotByGreedy(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
	{
		if (jobSubSet.empty())
		{
			// no need to update renderJobSlot
		    return nLeftMinute;
		}
		
		int nNextLeftMinute = nLeftMinute;
		// and we know it is not empty
		RenderJobSet::iterator theFirst;
		for (theFirst = jobSubSet.begin(); theFirst != jobSubSet.end(); theFirst ++)
		{
			// initialize the parameter
			int nTempNextLeftMin = nNextLeftMinute - theFirst->minute;

			if (nTempNextLeftMin == 0)
			{
				// we cannot expect anything better
				renderJobVector.push_back(*theFirst);				
				return 0;				
			}
			else
			{
				if (nTempNextLeftMin >= theFirst->minute)
				{
					//still possible for more
					renderJobVector.push_back(*theFirst);
					nNextLeftMinute = nTempNextLeftMin;
				}
				else
				{
					//it is time for us to search backward;
					break;
				}
			}
		}
		if (theFirst == jobSubSet.end())
		{
			return nNextLeftMinute;
		}

		// 
		if (nNextLeftMinute < theFirst->minute)
		{
			if (!renderJobVector.empty())
			{
				nNextLeftMinute += renderJobVector[renderJobVector.size() - 1].minute;
				renderJobVector.pop_back();
			}
			else
			{
				return nNextLeftMinute;
			}
		}
		FrameIndexRenderMinute node = *theFirst;
		int nMinLeftMinute = nNextLeftMinute;
		for (RenderJobSet::reverse_iterator it = jobSubSet.rbegin(); it != jobSubSet.rend(); it ++)
		{
			if (nNextLeftMinute >= it->minute)
			{
				renderJobVector.push_back(*it);
				return nNextLeftMinute - it->minute;
			}
		}
		
      	return nMinLeftMinute;
	}

	int findMaxFitSlotByRecursion(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
	{		
		if (jobSubSet.empty())
		{
			// no need to update renderJobSlot
		    return nLeftMinute;
		}
		int nMinLeftMinute;
		nMinLeftMinute = nLeftMinute;
		
		RenderJobVector minJobVector;
		minJobVector.assign(renderJobVector.begin(), renderJobVector.end());
		// and we know it is not empty
		for (RenderJobSet::iterator theFirst = jobSubSet.begin(); theFirst != jobSubSet.end(); theFirst ++)
		{

		// initialize the parameter
			int nNextLeftMinute = nLeftMinute - theFirst->minute;

			if (nNextLeftMinute < 0)
			{
				//we deliberately want to return negative to indicate there is no need to continue as our
				// job queue is sorted.
				return nNextLeftMinute;
			}			

			RenderJobSet nextRenderJobSet;
			
			RenderJobSet::iterator it = theFirst;
			// we can do this because jobSubSet is not empty 
			for (it ++ ; it != jobSubSet.end(); ++ it)
			{
				nextRenderJobSet.insert(*it);
			}
		
		    RenderJobVector tempJobVector;
			// copy the original result and add our first job at back		
			tempJobVector.assign(renderJobVector.begin(), renderJobVector.end());
			tempJobVector.push_back(*theFirst);

		    int nTempLeftMinute = findMaxFitSlot(nextRenderJobSet, nNextLeftMinute, tempJobVector);
			
			
		    if (nTempLeftMinute >= 0 && nTempLeftMinute < nMinLeftMinute)
		    {
				nMinLeftMinute = nTempLeftMinute;
				minJobVector.assign(tempJobVector.begin(), tempJobVector.end());
		    }
			if (nTempLeftMinute < 0)
			{
				// we know there is no chance for any try further
				//nMinLeftMinute = nTempLeftMinute;
				break;
			}
		    // remove stack
		    //renderJobVector.pop_back();
		}
		// this is what we find, or possible nothing changed
		renderJobVector.assign(minJobVector.begin(), minJobVector.end());		

      	return nMinLeftMinute;
	}

public:
	void printRenderJobSet(RenderJobSet& jobSet)
	{
		for (RenderJobSet::iterator it = jobSet.begin(); it != jobSet.end(); it ++)
		{
			printf("job: frameIndex=%d,renderMinute=%d\n", it->index, it->minute);
		}
	}

	RenderJobVectorVector Dispatch(RenderJobSet renderJobSet, RenderJobVector& finishedJobVector, int nMaxMinute)
	{
	   applyFinishedJobSet(renderJobSet, finishedJobVector);
	   RenderJobVectorVector result;

	   int nLeftMinute = nMaxMinute;
	   RenderJobVector renderJobVector; 
	   do
	   {
			nLeftMinute = findMaxFitSlot(renderJobSet, nMaxMinute, renderJobVector);
			if (renderJobVector.empty())
			{
				// cannot find any more fit job slot assignment, just quit
				
				break;
			}
			result.push_back(renderJobVector);
			for (int i = 0; i < renderJobVector.size(); i ++)
			{
			   renderJobSet.erase(renderJobVector[i]);
			}
			renderJobVector.clear();
	   }
	   while (true);
	   // let's print the unsolved jobs
	   printf("the rest unassigned jobs are:\n");
	   printRenderJobSet(renderJobSet);
	   return result;
	}
};
			
		    

		 
int main()
{   
    const int MaxJobNumber = 3000;
	const int MaxAllowedMinute = 240;
	RenderJobDispatch dispatch;
	RenderJobSet renderJobSet;
	RenderJobVector finishedJobVector;
	RenderJobVectorVector result;
	for (int i = 0; i < MaxJobNumber; i ++)
	{
	    FrameIndexRenderMinute node;
	    node.index = i;
	    node.minute = rand()%30 + 20;
	    renderJobSet.insert(node);
	    printf("job:index=%d, minute=%d\n", node.index,node.minute);
	}
	int counter = 0;
	printf("before starting:\n//////////////////////////////////////\n");
	dispatch.printRenderJobSet(renderJobSet);
	printf("\n\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n");


	do
	{
		dispatch.applyFinishedJobSet(renderJobSet, finishedJobVector);	
/*
		printf("before pass %d, the job set is:\n//////////////////////////////////////\n", counter++);
		dispatch.printRenderJobSet(renderJobSet);
		printf("\n\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n");
*/
        result = dispatch.Dispatch(renderJobSet, finishedJobVector, MaxAllowedMinute);
	    if (result.size() == 0)
	    {
			break;
	    }
	    // got a new job slot and 
	    // do rendering, assume we just finish one slot of job every time
	    // rendering...
	    
	    // finished one slot and insert into the finished job slot
	    printf("\n...rendering...\n");
	    printf("finished job is...\n");	 
		int total = 0;
	    for (int i = 0; i < result[0].size(); i ++)
	    {
			total += result[0][i].minute;
			printf("index=%d,minute=%d\n", result[0][i].index, result[0][i].minute);
			finishedJobVector.push_back(result[0][i]);
	    }
		printf("this job slot has %d minute left based on maximum minute %d allowed\n", MaxAllowedMinute - total, MaxAllowedMinute);
	}
	while (true);

	return 0;
}