#include "backtrack.h"

namespace bt{
	backtrack::backtrack() {}

	backtrack::backtrack(uint32_t graphType,uint32_t numVer,uint32_t numDef,uint32_t firstLabel,bool isAll)
	{
		this->theGraph=new semtd(graphType,numVer,numDef);
		this->graphType=graphType;
		this->usedLabels.resize(this->theGraph->TotalVer+1,false);
		this->IsSemt=false;
		setLabel(1,firstLabel);
		this->firstLabel=firstLabel;
		this->Result="";
		this->RecurseAll=isAll;
		this->pathLabel=this->startPath=this->endPath=0;
		switch(graphType)
		{
		case 4:
			{
				this->startPath=2;
				this->endPath=this->theGraph->NumVer;
				break;
			}
		case 3:
		case 5:
			{
				this->startPath=3;
				this->endPath=this->theGraph->NumVer;
				break;
			}
		}
	}

	inline void backtrack::setLabel(uint32_t verPos,uint32_t verLabel)
	{
		this->usedLabels[verLabel]=true;
		this->theGraph->SetVerLabel(verPos,verLabel);
	}

	inline void backtrack::removeLabel(uint32_t verPos)
	{
		this->usedLabels[this->theGraph->VerLabels[verPos]]=false;
		this->theGraph->RemoveVerLabel(verPos);
	}

	void backtrack::walk(uint32_t currentLevel)
	{
		if (this->IsProcessing)
		{
			if (currentLevel > this->theGraph->NumVer)
			{
				if (this->theGraph->IsSemt())
				{
					if(!this->RecurseAll)
					{
						this->IsProcessing = false;
					}
					this->Result += this->theGraph->Print(1);
					//setDual();
					//this->Result+="\nDual:\n"+this->theGraph->Print()+"\n";
					//setDual(); //undo the damage
					this->IsSemt = true;
				}
				removeLabel(currentLevel - 1);
			}
			else
			{
				//List<int> availableLabels = new List<int>();
				vector<uint32_t> availableLabels;
				uint32_t start=1;
				uint32_t end=this->theGraph->TotalVer;
				if(currentLevel==2 && this->firstLabel != this->theGraph->TotalVer)
				{
					if(this->graphType==3)
						start=end; //optimization for wheel
					else if(this->graphType==5)
						start=this->firstLabel+1;
				}
				else if(this->startPath!=0)
				{
					if(currentLevel==this->endPath)
						start=this->pathLabel+1; //remove possibility for reversed path labeling
					else if(currentLevel==this->startPath && start<end)
						end=this->theGraph->TotalVer-1; //no need to test last label as it'll be checked already on all previous cases
				}
				for (uint32_t i = start; i <= end; i++)
					if (!this->usedLabels[i])
						availableLabels.push_back(i);
				if(availableLabels.size()>0)
				{
					for (int32_t x = availableLabels.size()-1; x >= 0; x--)
					{
						if((this->startPath!=0) && (currentLevel==this->startPath))
							this->pathLabel=availableLabels[x];
						if (this->theGraph->IsValidToLabel(currentLevel, availableLabels[x]))
						{
							setLabel(currentLevel,availableLabels[x]);
							walk(currentLevel + 1);
						}
						if (!this->IsProcessing)
							break;
					}
				}
				if (currentLevel != 2) { removeLabel(currentLevel - 1); }
			}
		}
	}
	void backtrack::Walk()
	{
		if(this->theGraph->numDef>=this->theGraph->MinDef())
		{
			this->IsProcessing=true;
			walk(2);
		}
		else
		{
			this->IsSemt=false;
		}
	}
}