0001 /****************************************************************************************** 0002 * Test of B-Tree 0003 ******************************************************************************************/ 0004 #include "BTree_test.h" 0005 0006 /****************************************************************************************** 0007 * Test a BTree 0008 ******************************************************************************************/ 0009 template <typename T> void testBTree ( int order, int n ) { 0010 BTree<T> bt ( order ); 0011 while ( bt.size() < n ) { 0012 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0013 switch ( dice ( 3 ) ) { 0014 case 0: { //查找,成功率 <= 33.3% 0015 printf ( "Searching for " ); print ( e ); printf ( " ... " ); 0016 BTNodePosi(T) p = bt.search ( e ); 0017 printf ( p ? "Found\n" : "Not found\n" ); 0018 break; 0019 } 0020 case 1: { //删除,成功率 <= 33.3% 0021 printf ( "Removing " ); print ( e ); printf ( " ... " ); 0022 bt.remove ( e ) ? 0023 printf ( "Done\n" ), print ( bt ) : 0024 printf ( "Not exists\n" ); 0025 break; 0026 } 0027 default: {//插入,成功率 == 100% 0028 printf ( "Inserting " ); print ( e ); printf ( " ... " ); 0029 int oldSize = bt.size(); 0030 bt.insert ( e ) ? 0031 printf ( "Done\n" ), print ( bt ) : 0032 printf ( "Dup key\n" ); 0033 break; 0034 } 0035 } 0036 } 0037 while ( bt.size() > 0 ) { 0038 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0039 printf ( "Removing " ); print ( e ); printf ( " ... " ); 0040 bt.remove ( e ) ? 0041 printf ( "Done\n" ), print ( bt ) : 0042 printf ( "not exists\n" ); 0043 } 0044 } 0045 0046 /****************************************************************************************** 0047 * 测试主入口 0048 ******************************************************************************************/ 0049 int main ( int argc, char* argv[] ) { 0050 if ( 3 > argc ) { printf ( "Usage: %s <order of B-tree> <size of test>\a\a\n", argv[0] ); return 1; } 0051 int order = atoi ( argv[1] ); if ( order < 3 ) { printf ( "Make sure the order (%d) is no less than 3.\a\a\n", order ); return 1; } 0052 int size = atoi ( argv[2] ); if ( size < 0 ) { printf ( "Make sure the size (%d) is no less than 0.\a\a\n", size ); return 1; } 0053 srand ( ( unsigned int ) time ( NULL ) ); 0054 testBTree<int> ( atoi ( argv[1] ), atoi ( argv[2] ) ); //元素类型、比较器可以在这里任意选择 0055 return 0; 0056 }