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