demo_btree.cc

用Borland C写的B-Tree算法

/*****************************************************************************
 * btree-mem-C/demo_btree.cc
 *
 * COPYRIGHT (c) 1995, 1997 by David Van Wagner ALL RIGHTS RESERVED
 * Source and executables may be distributed under the terms of the GNU
 * General Public License version 2, see the file COPYING for details.
 *
 * [e-mail]
 * http://alumni.cse.ucsc.edu/~davevw/
 *****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include "btree.h"
#include "btkey.h"

BTREE_ROOT<BTREE_KEY_STR> *tree;

void menu_display()
{
	cout << "a=add, c=count d=delete, e=empty, f=find, m=menu, p=print, q=quit"
		<< endl;
}

void menu_response(char& c, char *dest, int size)
{
	char s[1024];

	cout << '>' << ' ' << flush;
	*dest = '\0';
	cin.width(sizeof(s));
	cin >> s;
	c = *s;
	if (*s != '\0')
		strncpy(dest, s+1, size);
}

void menu_do(char c, const char *s)
{
	BTREE_POS pos;
	BTREE<BTREE_KEY_STR> *node;
	BTREE_KEY_STR key(s);
	long value=atol(s);
	long before, after;
	BTREE_POS order=tree->get_order();

	switch (c) {
		case 'a':
			before = tree->get_count();
			node = tree->add(key, pos);
			after = tree->get_count();
			assert(before+1 == after);
			cout << "added " << key << " at " << (void *)node << ", index "
				<< int(pos) << endl;
			break;
		case 'c':
			cout << "count of elements in tree = " << tree->get_count() << endl;
			break;
		case 'd':
			node = tree->find(key, pos);
			if (pos == -1)
				cout << key << " not found" << endl;
			else {
				before = tree->get_count();
				tree->remove(key);
				after = tree->get_count();
				assert(before-1==after);
			}
			break;
		case 'e':
			delete tree;
			if (value > 2 && value%2 == 1)
				order = value;
			tree = new BTREE_ROOT<BTREE_KEY_STR>(order);
			after = tree->get_count();
			assert(after == 0);
			break;
		case 'f':
			node = tree->find(key, pos);
			if (pos == -1)
				cout << key << " not found" << endl;
			else
				cout << "found at " << (void *)node << ", index " << int(pos)
					<< endl;
			break;
		case 'p':
			tree->display2(0);
			break;
		case 'm':
		default:
			menu_display();
			break;
	}
}

int main(int /*argc*/, char */*argv*/[])
{
	char c;
	char s[80];

	tree = new BTREE_ROOT<BTREE_KEY_STR>(3);

	cout << "demo_btree" << endl << endl;
	menu_display();
	do {
		menu_response(c, s, sizeof(s));
		if (c != 'q')
			menu_do(c, s);
	} while (c != 'q');

	delete tree;

	return 0;
}