0001 #include "Splay_test.h"
0002 
0003 template <typename T> void testSplayPeriod( int n ) { //周期性访问测试
0004    Splay<T> splay;
0005    for ( int i = 0; i < n; i++ ) splay.insert ( ( T ) i ); print ( splay );
0006    for ( int i = 0; i < n; i++ ) { splay.search ( ( T ) i ); print ( splay ); }
0007 }
0008 
0009 template <typename T> void testSplayRandom( Rank n ) { //随机访问测试
0010    Splay<T> splay;
0011    while ( splay.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 ( " ...\n" );
0016             splay.search ( e ) ?
0017             printf ( "Found with" ), print ( splay.root() ), printf ( "\n" ) :
0018             printf ( "Not found\n" );
0019             break;
0020          }
0021          case 1: { //删除，成功率 <= 33.3%
0022             printf ( "Removing " ); print ( e ); printf ( " ...\n" );
0023             splay.remove ( e ) ?
0024             printf ( "Removal done\n" ) :
0025             print ( e ), printf ( " not exists\n" );
0026             break;
0027          }
0028          default: {//插入，成功率 == 100%
0029             printf ( "Inserting " ); print ( e ); printf ( " ...\n" );
0030             splay.insert ( e );
0031             ( e == splay.root()->data ) ?
0032             printf ( "Insertion done with" ), print ( splay.root() ), printf ( "\n" ) :
0033             print ( e ), "duplicated";
0034             break;
0035          }
0036       } //switch
0037       print ( splay ); //无论调用哪个接口，Splay都会自我调整形态，故需统一输出
0038    } //while
0039    while ( splay.size() > 0 ) {
0040       T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e
0041       printf ( "Removing " ); print ( e ); printf ( " ...\n" );
0042       splay.remove ( e ) ? printf ( "Removal done\n" ), print ( splay ) : print ( e ), printf ( " not exists\n" );
0043    }
0044 } //课后：利用这一接口，针对不同分布的访问，验证课上对Splay分摊分析的结论
0045 
0046 int main( int argc, char* argv[] ) { //测试主入口
0047    if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; }
0048    srand((unsigned int)time(NULL)); //随机种子
0049    //srand( 31415926 ); //固定种子（假种子，调试用）
0050    testSplayRandom<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择
0051    testSplayPeriod<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择
0052    return 0;
0053 }