Population

DFSArray

    A.First Edition

    This is my first edition of my DFS class implemented with an array. Or you can call it second version of standard

    DFS, third version of original DFS class.

    B.The problem

Does anybody regard array has higher efficiency than linked list? Yes, I think so. Linked list is using pointer
¡¡
to access an address then the value, or the address is used to access real value. This is typical indirect
¡¡
addressing mode, right? However, array is simply a kind of offset from beginning address of an array. This the
¡¡
reason why I want to re-implement my DFS class with array instead of linked list.
¡¡
C.The idea of program

    There is nothing special about this new version except that an internal static array of DFS* is used to store

    all nodes and all nodes is accessed with the index of this array. Most features of old standard DFS class were

    kept.

    D.The major functions

    1. void DFS::beginCount(int max, bool findall)

    This major public function sets up the searching maximum depth and option if all result should be searched.

    Whenever a new level of new nodes are generated, move first to the first son node and test user-defined function--

    evaluate() to see if result reached. After show result, test if all result should be searched. Then test if user-

    defined maximum level is reached. If yes, try next brother node, then rebound for higher level nodes. When going

    upper level, delete all those visited nodes to save memory.

    2. void DFS::backTrack()

    This utility function is quite useful and maybe used repeatedly in different situations. It save all data of nodes

    in an internal array.

    E.Further improvement

    1. Are you kidding? For such a trivial program?

    ¡¡

    #include <iostream>

    using namespace std;

    const int MaxSonCount=8;

    const int MaxLevel =20;

    const int MaxOptions = 10;

    const int MaxNodeCount = 1000;

    class DFS
    {
    private:
    	void initialize(DFS* now);
    	static DFS* nodeList[MaxNodeCount];
    	static bool findAll;
    	static int optionArray[MaxOptions];
    	static int optionCount;
    	static char** nameString;
    	static int solutionCount;
    	static int maxLevel;
    	static int domino;
    	void addSon(int sonData);
    	bool touchDown();
    	void setMaxLevel(int max) { maxLevel = max;}
    	DFS* upDate();
    	bool hasBrother();
    	DFS* nextBrother();
    	bool generate();
    	DFS* findNext();
    	DFS* getNode(int theIndex){return nodeList[theIndex];}
    	void putNode(int theIndex) { nodeList[theIndex] = this;}
    	DFS* getParent(){return getNode(parent);}
    	bool hasParent(){return parent!=-1;}
    protected:
    	int parent;
    	int sonCount;
    	int sonIndex;
    	int son;
    	int depth;
    	int index;//index in nodeList
    	int data;
    	void backTrack();
    	static int trackRecord[MaxLevel];
    	virtual DFS* createSon();
    	virtual bool validateOption(int sonData);
    	virtual void onLeave();
    	virtual bool evaluate();
    	virtual void collectResult();
    public:
    	int getSolutionCount(){ return solutionCount;}
    	void setOptions(int* array, int size);
    	void setNameStr(char** str){nameString = str;}
    	void beginCount(int max, bool findall=false);
    };

    int DFS::domino = 0;
    bool DFS::findAll = false;
    int DFS::maxLevel = 0;
    int DFS::optionArray[MaxOptions] = {0};
    char** DFS::nameString=NULL;
    int DFS::solutionCount = 0;
    int DFS::optionCount = 0;
    DFS* DFS::nodeList[MaxNodeCount] = {NULL};
    int DFS::trackRecord[MaxLevel]= {0};

    enum AxixType
    	{X,Y,Z};
    char* directionString[3] = {"X","Y","Z"};
    int restrict[3] = {3, 2, 4};
    int axis[3] = {X,Y,Z};

    class SpaceSpider: public DFS
    {
    protected:
    	virtual DFS* createSon();
    	virtual bool validateOption(int sonData);
    //	virtual void onLeave();
    	virtual bool evaluate();
    //	virtual void collectResult();

    };

    int main()
    {
    	SpaceSpider R;
    	R.setOptions(axis, 3);
    	R.setNameStr(directionString);
    	R.beginCount(9, true);
    	cout<<"Total number is "<<R.getSolutionCount()<<endl;

    	return 0;
    }

    DFS* SpaceSpider::createSon()
    {
    	DFS* ptr= new SpaceSpider;
    	return ptr;
    }

    bool SpaceSpider::validateOption(int sonData)
    {
    	int temp[3] = {0};
    	backTrack();
    	temp[sonData]++;
    	for (int i=0; i<depth; i++)
    	{
    		temp[trackRecord[i]]++;
    		if (temp[trackRecord[i]]>restrict[trackRecord[i]])
    		{
    			return false;
    		}
    	}
    	return true;
    }

    bool SpaceSpider::evaluate()
    {
    	return depth==9;
    }

    //I don't know what extra work to be for the time being
    bool DFS::evaluate()
    {
    	return true;
    }

    bool DFS::touchDown()
    {
    	return depth==maxLevel;
    }

    void DFS::onLeave()
    {
    	DFS* ptr =this;
    	int end = ptr->index;
    	int start;
    	if (ptr->hasParent())
    	{
    		start = ptr->getParent()->son;
    		for (int i= start; i<=end;i++)
    		{
    			ptr = getNode(i);
    			delete ptr;
    			nodeList[i] = NULL;
    		}
    		domino = domino + start - end -1;
    	}
    }

    void DFS::backTrack()
    {
    	DFS* ptr = this;

    	while (ptr->hasParent())
    	{
    		trackRecord[ptr->depth-1] = ptr->data;
    		ptr = ptr->getParent();
    	}
    }

    //a stack
    void DFS::collectResult()
    {
    	backTrack();
    	cout<<"The route is:";
    	for (int i=0; i<depth; i++)
    	{
    		cout<<nameString[trackRecord[i]]<<", ";
    	}
    	cout<<"It is number:"<<solutionCount++;
    	cout<<endl;
    }

    void DFS::setOptions(int *array, int size)
    {
    	optionCount = size;
    	for (int i=0; i<size; i++)
    	{
    		optionArray[i] = *(array+i);
    	}
    }

    //this is supposed to be overrided by user
    bool DFS::validateOption(int sonData)
    {
    	return true;
    }

    void DFS::beginCount(int max, bool findall)
    {
    	DFS* ptr = this;
    	setMaxLevel(max);
    	findAll = findall; //setup if want all result
    	initialize(this);

    	while (ptr!=NULL)
    	{
    		if (ptr->generate())
    		{
    			ptr = ptr->upDate();//move to first son
    			if (ptr->evaluate())
    			{
    				ptr->collectResult();
    				if (!findAll)
    				{
    					break;
    				}
    				else
    				{
    					ptr = ptr->findNext();
    				}
    			}
    			else
    			{
    				if (ptr->touchDown())
    				{
    					ptr=ptr->findNext();
    				}
    			}
    		}
    		else
    		{
    			ptr = ptr->findNext();
    		}
    	}
    	if (solutionCount==0)
    	{
    		cout<<"no solution!";
    	}
    }

    DFS* DFS::findNext()
    {
    	DFS* ptr = this;
    	DFS* dummy;
    	while (ptr!=NULL)
    	{
    		if (ptr->hasBrother())
    		{
    			return getNode(ptr->index+1);//next brother
    		}
    		else
    		{
    			if (ptr->hasParent())
    			{
    				dummy = ptr;
    				ptr = ptr->getParent(); //if
    				dummy->onLeave(); //only clear when go up one level
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    	return NULL;
    }

    bool DFS::generate()
    {
    	DFS* ptr= this;
    	bool result = false;
    	//this is preorder and I don't bother to
    	//give choices for midorder or postorder
    	for (int i=0; i< optionCount; i++)
    	{
    		if (validateOption(optionArray[i]))
    		{
    			addSon(optionArray[i]);
    			result = true;
    		}
    	}
    	return result;
    }

    DFS* DFS::upDate()
    {
    	//return first son
    	return getNode(son);
    }

    //must be override by user when inherited
    DFS* DFS::createSon()
    {
    	DFS* ptr = new DFS;
    	return ptr;
    }

    void DFS::addSon(int sonData)
    {
    	if (sonCount+1<MaxSonCount)
    	{
    		if (domino==MaxNodeCount)
    		{
    			cout<<"Exceeds limit of node list"<<endl;
    			return;
    		}
    		DFS* ptr = createSon();
    		ptr->index = domino;//
    		ptr->putNode(domino);

    		if (sonCount==0)//if it is the first son
    		{
    			son = domino;//first son
    		}
    		domino++;
    		ptr->data = sonData;
    		ptr->sonCount = 0;
    		ptr->son = -1;//temporarily
    		ptr->parent = index;
    		ptr->depth = depth+1;
    		ptr->sonIndex = sonCount;
    		sonCount++;
    	}
    	else
    	{
    		cout<<"Exceed max of sons!";
    	}
    }

    void DFS::initialize(DFS* now)
    {
    	now->index =0;
    	now->depth = 0;
    	now->sonCount = 0;
    	now->sonIndex = -1;
    	now->parent = -1;
    	now->data = 0;
    	now->putNode(0); //put in list
    	domino++;
    }

    bool DFS::hasBrother()
    {
    	if (hasParent())
    	{
    		if (getParent()->sonCount > sonIndex+1)//has little brother
    		{
    			return true;
    		}
    	}
    	return false;
    }

    Running result of program:

    I want to test my new class, so I choose the old problem---the space spider who is crawling in 3-D for 9 steps in which it can only

    go X-axis 3 steps, Y-axis 2 steps, Z-axis 4 steps. This problem has been solved before.

    ...

    ...

    The route is:Z, Z, Z, X, Z, Y, X, X, Y, It is number:1227
    The route is:Z, Z, Z, X, Z, Y, X, Y, X, It is number:1228
    The route is:Z, Z, Z, X, Z, Y, Y, X, X, It is number:1229
    The route is:Z, Z, Z, Y, X, X, X, Y, Z, It is number:1230
    The route is:Z, Z, Z, Y, X, X, X, Z, Y, It is number:1231
    The route is:Z, Z, Z, Y, X, X, Y, X, Z, It is number:1232
    The route is:Z, Z, Z, Y, X, X, Y, Z, X, It is number:1233
    The route is:Z, Z, Z, Y, X, X, Z, X, Y, It is number:1234
    The route is:Z, Z, Z, Y, X, X, Z, Y, X, It is number:1235
    The route is:Z, Z, Z, Y, X, Y, X, X, Z, It is number:1236
    The route is:Z, Z, Z, Y, X, Y, X, Z, X, It is number:1237
    The route is:Z, Z, Z, Y, X, Y, Z, X, X, It is number:1238
    The route is:Z, Z, Z, Y, X, Z, X, X, Y, It is number:1239
    The route is:Z, Z, Z, Y, X, Z, X, Y, X, It is number:1240
    The route is:Z, Z, Z, Y, X, Z, Y, X, X, It is number:1241
    The route is:Z, Z, Z, Y, Y, X, X, X, Z, It is number:1242
    The route is:Z, Z, Z, Y, Y, X, X, Z, X, It is number:1243
    The route is:Z, Z, Z, Y, Y, X, Z, X, X, It is number:1244
    The route is:Z, Z, Z, Y, Y, Z, X, X, X, It is number:1245
    The route is:Z, Z, Z, Y, Z, X, X, X, Y, It is number:1246
    The route is:Z, Z, Z, Y, Z, X, X, Y, X, It is number:1247
    The route is:Z, Z, Z, Y, Z, X, Y, X, X, It is number:1248
    The route is:Z, Z, Z, Y, Z, Y, X, X, X, It is number:1249
    The route is:Z, Z, Z, Z, X, X, X, Y, Y, It is number:1250
    The route is:Z, Z, Z, Z, X, X, Y, X, Y, It is number:1251
    The route is:Z, Z, Z, Z, X, X, Y, Y, X, It is number:1252
    The route is:Z, Z, Z, Z, X, Y, X, X, Y, It is number:1253
    The route is:Z, Z, Z, Z, X, Y, X, Y, X, It is number:1254
    The route is:Z, Z, Z, Z, X, Y, Y, X, X, It is number:1255
    The route is:Z, Z, Z, Z, Y, X, X, X, Y, It is number:1256
    The route is:Z, Z, Z, Z, Y, X, X, Y, X, It is number:1257
    The route is:Z, Z, Z, Z, Y, X, Y, X, X, It is number:1258
    The route is:Z, Z, Z, Z, Y, Y, X, X, X, It is number:1259
    Total number is 1260
    Press any key to continue

    ¡¡