command.cpp

我的红黑树的c++实现。主要特点是可以用dot工具把红黑树画出来

// file command.cpp
//created by alpha 2008.11.3

#include "../headers/command.h"
#include "../headers/control.h"
#include "../headers/rbtree.h"
#include "../headers/bstree.h"
#include "../headers/timer.h"
#include "../headers/dot.h"
#include <map>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;
typedef map<string, int>::value_type cmdValType;
typedef string::size_type strSizeType;

command::command(string s)
{
	strSizeType loc = s.find(" ",0);
	if(loc == string::npos)
		cmd = s;
}
bool command::control()
{
	init();
	int i = -1;
	if(m.count(cmd))
		i = m[cmd];
	else
		cerr<<"bad command!\n";
	switch(i)
	{
		case 0:
			return false;
		case 1:
			setup();		break;
		case 2:
			inserttest();	break;
		case 3:
			deletetest();	break;
		case 4:
			randomtest();	break;
		case 5:
			average();		break;
		case 6:
			keyrank();		break;
		case 7:	
			help();			break;
		case 8:
			clear();		break;
		default:
			break;
	}
	return true;
}

void command::init()                           //enrol  commands
{
	m.insert(cmdValType("quit",0));
	m.insert(cmdValType("setup",1));
	m.insert(cmdValType("test",2));
	m.insert(cmdValType("deletetest",3));
	m.insert(cmdValType("random",4));
	m.insert(cmdValType("average",5));
	m.insert(cmdValType("keyrank",6));
	m.insert(cmdValType("help",7));
	m.insert(cmdValType("clear",8));
}

void command::setup()
{
	system("graphviz.exe");
}

void command::inserttest()
{
	controlInsert = 1;           //open -ins option
	rbtree t;
	cout<<"insert 8，11，17，15，6，1，22，25，27 in turn:\n";
	t.insert(8);
	t.insert(11);
	t.insert(17);
	t.insert(15);
	t.insert(6);
	t.insert(1);
	t.insert(22);
	t.insert(25);
	t.insert(27);
	t.print();
	cout<<"the bh of test rbtree is "<<t.getBh()<<endl;
	cout<<"delete node 15:\n";
	t.delNode(15);
	t.print();
	cout<<"the bh of test rbtree is "<<t.getBh()<<endl;
	controlInsert = 0;         //close -ins option
	return;
}

void command::deletetest()
{
	return;
}

void command::randomtest()
{
	vector<int> rand;
	cout<<"creating random nodes...";
	int size = 300000;
	int i = 0;
	Timer rbtm,bstm;
	while(i < size)
		rand.push_back(++i);
	random_shuffle(rand.begin(), rand.end());
	cout<<"\t\tcreat finished\n";
	rbtree rbt;
	bstree bst;
	//insert and find in bstree
	cout<<"inserting nodes to bstree...";
	for (i = 0; i < size; i++)
		bst.insert(rand[i]);
	cout<<"\t\tinsert finished\n";
	cout<<"finding 15000 in bstree...";
	bstm.Start();
	bool flag = bst.find(15000);
	bstm.End();
	if (flag)
		cout<<"\t\tfound 15000 in bstree!\n";
	//insert and find in rbtree
	cout<<"inserting nodes to rbtree...";
	for(i = 0; i < size; i++)
	{
		rbt.insert(rand[i]);
	}
	cout<<"\t\tinsert finished\n";
	cout<<"finding 15000 in rbtree...";
	rbtm.Start();	
	flag = rbt.find(15000);
	rbtm.End();
	if (flag)
		cout<<"\t\tfound 15000 in rbtree!\n";

	long rbtime = rbtm.costTime;
	long bstime = bstm.costTime;
	cout<<"cost of finding 15000 in RED_BLACK_TREE with 300000 nodes is "<<rbtime<<" us"<<endl;
	cout<<"cost of finding 15000 in BINARY_SEARCH_TREE with 300000 nodes is "<<bstime<<" us"<<endl;

	cout<<endl;
	return;
}

void command::average()
{
	float rbaver = 0;
	float bsaver = 0;
	for(int i = 0; i< 5; i++)
	{
		vector<int> rand;
		cout<<"creating random nodes...";
		int size = 300000;
		int i = 0;
		Timer tm;
		while(i < size)
			rand.push_back(++i);
		random_shuffle(rand.begin(), rand.end());
		cout<<"\t\tcreat finished\n";
		bsaver += rtest_bstree(rand);
		rbaver += rtest_rbtree(rand);
		cout<<endl;
	}
	rbaver /= 5.0;
	bsaver /= 5.0;
	cout<<"\naverage time of finding 15000 in RED_BLACK_TREE with 300000 nodes is "<<rbaver<<" us";
	cout<<"\naverage time of finding 15000 in BINARY_SEARCH_TREE with 300000 nodes is "<<bsaver<<" us\n";
}

void command::keyrank()
{
	rbtree t;
	for(int i = 1; i < 9; i++)
	{
		t.insert(i);
		cout<<"inserting "<<i<<endl;
	}
	cout<<"\nOS_KEY_RANK of 6 is "<<t.keyrank(6)<<endl;
}

float command::rtest_rbtree(vector<int> &rand)
{
	int i;
	int size = rand.size();
	rbtree t;
	cout<<"inserting nodes to rbtree...";
	for(i = 0; i < size; i++)
	{
		t.insert(rand[i]);
	}
	cout<<"\t\tinsert finished\n";
	cout<<"finding 15000 in rbtree...";
	Timer tm;
	tm.Start();	
	bool flag = t.find(15000); 
	tm.End();
	if(flag)
		cout<<"\t\tfound 15000!\n";
	long time = tm.costTime;
	cout<<"cost of finding 15000 in RED_BLACK_TREE with 300000 nodes is "<<time<<" us"<<endl;
	return time;	
}
float command::rtest_bstree(vector<int> &rand)
{
	int i;
	int size = rand.size();
	bstree t;
	cout<<"inserting nodes to rbtree...";
	for(i = 0; i < size; i++)
		t.insert(rand[i]);
	cout<<"\t\tinsert finished\n";
	Timer tm;
	cout<<"finding 15000 in rbtree...";
	tm.Start();
	bool flag = t.find(15000); 
	tm.End();
	if(flag)
		cout<<"\t\tfound 15000!\n";
	long time = tm.costTime;
	cout<<"cost of finding 15000 in BINARY_SEARCH_TREE with 300000 nodes is "<<time<<" us"<<endl;
	return time;
}

void command::help()
{
	cout<<"\nrbtree v1.0\n";
	cout<<"Author: alpha\n\n";
	cout<<"arguments:\n";
	cout<<"You can open options below in command window by typing \'rbtree -ins -dot\'\n";
	cout<<"-ins:\tdraw JPG files to show process of inserting nodes;\n\tthis option is automatically opened when running \'test\' command\n";
	cout<<"\tWARNING:\n\tdon\'t open this option when inserting thousands of nodes,\n\tthat will exhaust your CPU\n";
	cout<<"-dot:\tkeep dot documents which generated to draw JPG files;\n";
	cout<<"\ncommands:\n";
	cout<<"help:\tget help;\n";
	cout<<"quit:\tquit the program;\n";
//	cout<<"setup:\tinstall the \'graphviz\' software;\n";
	cout<<"clear:\tclear command window;\n";
	cout<<"test:\ttest insert nodes to rbtree\n";
	cout<<"\tinsert 8，11，17，15，6，1，22，25，27 in turn, \n \
\toutput the rbtree in command window,\n \
\tand draw *.jpg file to show the process if installed \'graphviz\',\n \
\tand then delete node 15 for testing;\n";
//	cout<<"deletetest\n";
	cout<<"random:\tgenerate 300000 numbers and arrange them in random order,\n \
\tand then insert them to rbtree & bstree.\n \
\tThen timing the cost of finding 15000 in them;\n";
	cout<<"average: execute \'random\' five times and calculate the average cost;\n";
	cout<<"keyrank: insert 1-8 keys into OSTREE based on rbtree,\n\
\t and lookup the result of OS_KEY_RANK of 6\n";
	cout<<endl;
}

void command::clear()
{
	system("CLS");
}