regress.cc

用Borland C写的B-Tree算法

/*****************************************************************************
 * btree-mem-C/regress.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 "btree.h"
#include "btkey.h"
#include <iostream.h>

int order;
int limited;
int limit;

void conv_units(double &value, char * &units)
{
	if (value >= 60) {
		value /= 60;
		if (value >= 60) {
			value /= 60;
			if (value >= 24) {
				value /= 24;
				units = "days";
			} else
				units = "hours";
		} else
			units = "minutes";
	} else
		units = "seconds";
}

void test_add(int count, int *nums)
{
	BTREE_ROOT<BTREE_KEY_LONG> btree(order);
	static int last_count=0;
	static int sub_count=0;
	static time_t last_time=time(NULL);
	int i;

	if (count==last_count)
		++sub_count;
	else {
		if (last_count > 0) {
			time_t now=time(NULL);
			double dur=now-last_time;
			double next_dur=dur*count;
			char *units, *next_units;

			last_time = now;
			cout << last_count << " #" << sub_count << " successful at "
				<< ctime(&now);
			conv_units(dur, units);
			conv_units(next_dur, next_units);
			cout << ' ' << dur << ' ' << units;
			if (limited && count > limit) {
				cout << endl;
				exit(0);
			} else {
				cout << ", next result in " << next_dur << ' ' << next_units
					<< endl;
			}
		}
		sub_count = 1;
	}

	for (i=0; i<count; ++i) {
		BTREE_POS pos;
		long key;

		key=nums[i];
		btree.add(key, pos);
	}

	assert(btree.get_count() == count);

	for (i=0; i<count; ++i) {
		BTREE_POS pos;
		BTREE<BTREE_KEY_LONG> *found;
		long key;

		key=nums[i];
		found = btree.find(key, pos);
		assert(pos >= 0);
		assert(found != NULL);
	}

	last_count = count;
}

void permute(int count, int *nums_taken, int remaining, int *nums_order)
{
	int i;

	if (count==remaining) {
		assert(nums_taken == NULL);
		assert(nums_order == NULL);
		nums_taken = new int[count];
		for (i=0; i<count; ++i)
			nums_taken[i] = 0;
		nums_order = new int[count];
	}

	for (i=0; i<count; ++i) {
		if (!nums_taken[i]) {
			nums_taken[i] = 1;
			nums_order[count-remaining] = i+1;
			if (remaining == 1)
				test_add(count, nums_order);
			else
				permute(count, nums_taken, remaining-1, nums_order);
			nums_taken[i] = 0;
		}
	}

	if (count==remaining) {
		delete [] nums_taken;
		delete [] nums_order;
	}
}

int main(int argc, char *argv[])
{
	int count;
	char *order_env;

	if (argc > 1) {
		limited = 1;
		limit = atoi(argv[1]);
	} else {
		limited = 0;
		limit = 0;
	}

	order_env = getenv("BTREEORDER");
	if (order_env != (char *)NULL) {
		order = atoi(order_env);
		if (order < 3 || order%2 == 0)
			order = 3;
	} else
		order = 3;

	cout << "regression testing, adding to " << order << "-order B-Tree" <<endl;

	for (count=1; 1; ++count)
		permute(count, NULL, count, NULL);
}