tree.cpp

模拟linux下的shell中的目录系统

#include<iostream>
#include<string>
#include<cctype>
#include<iomanip>
using namespace std;

enum FILE_TYPE{ DIRECTORY, COMMONFILE };

struct TreeNode
{
	string fileName;
	FILE_TYPE fileType;
	TreeNode *childList;
	TreeNode *father;
	int childSize;
	TreeNode *brother;
	TreeNode( string name, TreeNode *child, int size, TreeNode *brother )
	: fileName( name ), childList( child ), childSize( size ), brother( brother ) {}
};

class MulChildTree
{
public:
	MulChildTree()
 	{	
		root = new TreeNode( "root", NULL, 0, NULL ); 
		root->father = NULL;
	}
	TreeNode* getBasicAddr() {	return root;	}
	bool isEmpty() {	return root == NULL;	}
	void insertChild( TreeNode *curAddr, string name ) 
	{
		curAddr->childList = new TreeNode( name, NULL, 0,  curAddr->childList );
		curAddr->childList->father = curAddr;
		curAddr->childSize ++;
	}
	bool moveTo( TreeNode *&curAddr, string fileName )
	{
		for ( TreeNode *itr = curAddr->childList; itr != NULL; itr = itr->brother )
			if ( itr->fileName ==  fileName  )
			{
				itr->father = curAddr;
				curAddr = itr;
				return true;
			}

		return false;
	}
	TreeNode* moveBack( TreeNode *curAddr )
	{
		if ( curAddr == root )
			return root;
		else
			return curAddr->father;
	}
	bool find( TreeNode *curAddr, string fileName )
	{
		for ( TreeNode *itr = curAddr->childList; itr != NULL; itr = itr->brother )
			if ( itr->fileName == fileName )
				return true;

		return false;
	}
	void showChild( TreeNode *curAddr )
	{
		for ( TreeNode *itr = curAddr->childList; itr != NULL; itr = itr->brother )
			cout << itr->fileName << " ";
		cout << endl;
	}
	void showChildAbsent( TreeNode *curAddr )
	{
		showChildAbs( curAddr->childList );
		cout << endl;
	}
	void printTree()
	{
		if ( root != NULL )
		{
			cout << root->fileName;
			printTree( root, root->fileName.length(), 0 );
			cout << endl;
		}
	}
	void printPathLn( TreeNode *curAddr )
	{
		printPath( curAddr );
		cout << endl;
	}
	bool deleteDir( TreeNode *curAddr, string fileName )
	{
		if ( deleteDirR( curAddr->childList, fileName ) )
		{
			curAddr->childSize --;
			return true;
		}
		else
			return false;
	}
	void deleteAll() 
	{	
		deleteAll( root );
		root = NULL;
	}
private:
	TreeNode *root;

	struct LineInfo
	{
		int pos;
		bool have;
	}infoList[ 1000 ];
	
	int printLineInfo( int level )
	{
		int pre = 0;
		for ( int i = 0; i < level; i ++ )
		{
			if ( infoList[ i ].have )
				cout << setw( infoList[ i ].pos - pre ) << '|';
			else
				cout << setw( infoList[ i ].pos - pre ) << ' ';
			pre = infoList[ i ].pos;
		}

		return pre;
	}
	void printTree( TreeNode *cur, int curPos, int level )
	{
		if ( cur-> childSize > 0 )
		{
			TreeNode *itr = cur->childList;
			cout << "___" << itr->fileName;
			infoList[ level ].pos = curPos + 2;
			if ( cur->childSize == 1 )
				infoList[ level ].have = false;
			else
				infoList[ level ].have = true;
			printTree( itr, curPos + 3 + itr->fileName.length(), level + 1 );
			itr = itr->brother;

			int i = 1;
			for ( ; itr != NULL && i < cur->childSize; itr = itr->brother, i ++ )
			{
				cout << endl;
				int lastPos = printLineInfo( level );
				cout << setw( curPos - lastPos + 3 ) << " |_";
				cout << itr->fileName;

				if ( i != cur->childSize - 1 )
				{
					infoList[ level ].pos = curPos + 2;
					infoList[ level ].have = true;
				}
				else
				{
					infoList[ level ].pos = curPos + 2;
					infoList[ level ].have = false;
				}

				printTree( itr, curPos + 3 + itr->fileName.length(), level + 1 );
			}
		}
	}
	void deleteAll( TreeNode* cur )
	{
		if ( cur != NULL )
		{
			TreeNode *tmp;
			for ( TreeNode *itr = cur->childList; itr != NULL; itr = tmp )
			{
				tmp = itr->brother;
				deleteAll( itr );
			}

			delete cur;
		}
	}
	bool deleteDirR( TreeNode *&t, string fileName )
	{
		if ( t == NULL )
			return false;
		else if ( t->fileName == fileName )
		{
			TreeNode *tmp = t->brother;
			deleteAll( t );
			t = tmp;

			return true;
		}
		else
			return deleteDirR( t->brother, fileName );
	}
	void showChildAbs( TreeNode *curAddr )
	{
		if ( curAddr != NULL )
		{
			showChildAbs( curAddr->brother );
			cout << curAddr->fileName << " ";
		}

	}
	void printPath( TreeNode *curAddr )
	{
		if ( curAddr != NULL )
		{
			printPath( curAddr->father );
			cout << curAddr->fileName << '/';
		}
		else
			cout << '/';
	}

};

MulChildTree test;
TreeNode *curAddr;

bool dealCmd ()
{
	const int BUF_SIZE = 1000;
	char cmd[ BUF_SIZE ];
	char cmdHead[ BUF_SIZE ], cmdPara[ BUF_SIZE ];
	gets( cmd );
	
	if ( curAddr == NULL )
		return false;
	
	if ( !strcmp( cmd, "ls" ) )
	{
		if ( curAddr->childSize > 0 )
			test.showChildAbsent( curAddr );
	}
	else if ( !strcmp( cmd, "exit" ) )
		return false;
	else if ( !strcmp( cmd, "dirTree" ) )
		test.printTree();
	else if ( !strcmp( cmd, "pwd" ) )
		test.printPathLn( curAddr );
	else if ( !strcmp( cmd, "clear" ) )
		printf( "\033[H\033[J" );
	else
	{
		int returnNum = sscanf( cmd, "%s %s", cmdHead, cmdPara );
		if ( !strcmp( cmdHead, "cd" ) )
		{
			if ( returnNum < 2 )
			{
				cout << "missing paramater!" << endl;
				return true;
			}
			if ( !strcmp( cmdPara, ".." ) )
			{
				curAddr = test.moveBack( curAddr );
			}
			else if ( !test.moveTo( curAddr, cmdPara ) )
				cout << cmdPara << " is not exit!" << endl;
		}
		else if ( !strcmp( cmdHead, "mkdir" ) )
		{
			if ( returnNum < 2 )
			{
				cout << "missing paramater!" << endl;
				return true;
			}
			else if ( test.find( curAddr, cmdPara ) )
			{
				cout << cmdPara << " has already exit!" << endl;
			}
			else
				test.insertChild( curAddr, cmdPara );
		}
		else if ( !strcmp( cmdHead, "rm" ) )
		{
			if ( returnNum < 2 )
			{
				cout << "missing paramater!" << endl;
				return true;
			}
			else if ( !test.deleteDir( curAddr, cmdPara ) )
				cout << cmdPara << " don't exits!" << endl;
		}
	}

	return true;
}

int main()
{
	//cout << "Tree demenstration!" << endl;
    curAddr = test.getBasicAddr();

	cout << "xingxing@xingxing-laptop:";
	while ( dealCmd() )
	{
		cout << "xingxing@xingxing-laptop:";
	}
	
	/*
    cout << "THE FINAL TREE is" << endl;	
	test.printTree();
	cout << "END PRINT" << endl;
	*/
	test.deleteAll();

	return 0;	
}