0001 /******************************************************************************************
0002  * Test of RedBlack Tree
0003  ******************************************************************************************/
0004 #include "RedBlack_test.h"
0005 
0006 /******************************************************************************************
0007  * Test a RedBlack
0008  ******************************************************************************************/
0009 template <typename T> void testRedBlack( Rank n ) {
0010    RedBlack<T> rb;
0011    while ( rb.size() < n ) {
0012       T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e
0013       switch ( dice ( 6 ) ) {
0014          case 0: { //查找（概率 = 1/6）
0015             printf ( "Searching for " ); print ( e ); printf ( " ...\n" );
0016             BinNodePosi<T> p = rb.search ( e );
0017             p ?
0018             printf ( "Found with" ), print ( p ), printf ( "\n" ) :
0019             printf ( "Not found\n" );
0020             break;
0021          }
0022          case 1:
0023          case 2: { //删除（概率 = 2/6)
0024             printf ( "Removing " ); print ( e ); printf ( " ...\n" );
0025             rb.remove ( e ) ? printf ( "Done\n" ), print ( rb ) : printf ( "Not exists\n" );
0026             break;
0027          }
0028          default: { //插入（概率 = 3/6)
0029             printf ( "Inserting " ); print ( e ); printf ( " ...\n" );
0030             BinNodePosi<T> p = rb.insert ( e );
0031             if ( p->data != e ) { print ( p->data ); printf ( " <> " ); print ( e ); printf ( "\n" ); }
0032             printf ( "Done with" ), print ( p ), printf ( "\n" ), print ( rb );
0033             break;
0034          }
0035       }
0036    }
0037    while ( rb.size() > 0 ) {
0038       T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e
0039       printf ( "Removing " ); print ( e ); printf ( " ...\n" );
0040       rb.remove ( e ) ? printf ( "Done\n" ), print ( rb ) : printf ( "Not exists\n" );
0041    }
0042 }
0043 
0044 /******************************************************************************************
0045  * 测试主入口
0046  ******************************************************************************************/
0047 int main( int argc, char* argv[] ) {
0048    if ( 2 > argc ) { printf( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; }
0049    srand((unsigned int)time(NULL)); //随机种子
0050    //srand( 31415926 ); //固定种子（假种子，调试用）
0051    testRedBlack<int>( atoi( argv[1] ) ); //元素类型可以在这里任意选择
0052    return 0;
0053 }