0001 /******************************************************************************************
0002  * 测试位图
0003  ******************************************************************************************/
0004 int testBitmap( int n, int t ) {
0005    bool* B = new bool[n]; //常规位图
0006    Bitmap M ( n ); //高效位图
0007    while ( t-- > 0 ) { //重复使用位图多次
0008       memset ( B, 0, n * sizeof ( bool ) ); //逐位清零，O(n)
0009       M.reset(); //逻辑清零，O(1)
0010       for ( int i = 0; i < 3 * n; i++ ) { //反复地
0011          Rank k = dice ( n ); //在随机位置上
0012          if ( dice ( 2 ) ) { //以50%的概率插入
0013             B[k] = true; M.set ( k );
0014          } else { //或50%的概率清除
0015             B[k] = false; M.clear ( k );
0016          }
0017       }
0018       //M.set( 29 ); //有时可卖个破绽，以反向测试本测试程序
0019       int sz = 0; for ( int j = 0; j < n; j++ ) sz += B[j];
0020       printf( "\nM[] x %d %s %d\n", M.size(), ( M.size() == sz ? "==" : "<>" ), sz );
0021       for ( int j = 0; j < n; j++ ) printf ( "%c", M.test ( j ) ? 'x' : '.' );
0022       int k = 0;
0023       while ( k++ < n ) //逐位地对比
0024          if ( B[k] != M.test ( k ) ) //一旦发现不合
0025             break; //随即退出
0026       if ( k < n ) { //并报告（assert:: k == n+1）
0027          printf ( "\n B[]\n" );
0028          for ( int j = 0; j <= k; j++ ) printf ( "%c", B[j] ? 'x' : '.' );
0029          printf ( "\n M[] x %d\n", M.size() );
0030          for ( int j = 0; j <= k; j++ ) printf ( "%c", M.test ( j ) ? 'x' : '.' );
0031          printf ( "\n" );
0032       } else
0033          printf( "\nTest %4d OK\n", t );
0034    }
0035    delete [] B;
0036    return 0;
0037 }
0038 
0039 /******************************************************************************************
0040  * 测试位图
0041  ******************************************************************************************/
0042 int main( int argc, char* argv[] ) {
0043    if ( 3 > argc ) { printf ( "Usage: %s <bitmap size> <#test>\a\a\n", argv[0] ); return 1; }
0044    srand((unsigned int)time(NULL)); //随机种子
0045    //srand( 31415926 ); //固定种子（假种子，调试用）
0046    return testBitmap( max(0, atoi(argv[1])), max(0, atoi(argv[2]))); //启动测试
0047 }