0001 /******************************************************************************************
0002 * Test of DEPQ
0003  ******************************************************************************************/
0004 #include "DEPQ_test.h"
0005 
0006 void verify(SMMH<int> H) { //针对基于列表、向量以及左式堆实现的优先级队列，做统一测试
0007    Rank s = H.size();  Rank k = 0;
0008    while (++k < s) {
0009       if (isLC(k) && sib(k) < s  &&  H[k] > H[sib(k)]) break; //Property #0
0010       if (isLC(k) && lc(k) < s && H[k] > H[lc(k)]) break; //Property #1
0011       if (isLC(k) && ln(k) < s && H[k] > H[ln(k)]) break;
0012       if (isRC(k) && rc(k) < s && H[k] < H[rc(k)]) break; //Property #2
0013       if (isRC(k) && rn(k) < s && H[k] < H[rn(k)]) break;
0014    }
0015    if (k < s) { print(H);  printf("SMMP invalid at H[%d] = %d\n", k, H[k]);  exit(-1); }
0016 } //verify
0017 
0018 void test(Rank n) {
0019    SMMH<int> H; //init an empty DEPQ implemented as an SMMH
0020    while (H.size() < n) { //随机测试
0021       if (dice((Rank) 100) < 70) { //insert with a prob. of 70%
0022          int e = dice(7*n);
0023          H.insert(e);
0024       } else { //delMin or delMax with a prob. of 15% resp.
0025          if (1 < H.size())
0026             if (dice((Rank) 100) < 50) {
0027                int e = H.delMin();
0028             } else {
0029                int e = H.delMax();
0030             }
0031       }
0032       verify(H);
0033    }
0034    while (1 < H.size()) { //delMin or delMax with a prob. of 50% resp.
0035       if (dice((Rank) 100) < 50) {
0036          int e = H.delMin();
0037       } else {
0038          int e = H.delMax();
0039       }
0040       verify(H);
0041       if (H.size() < 16) { print(H);  printf("\n"); }
0042    }
0043 } //test
0044 
0045 int main(int argc, char* argv[]) { //优先级队列测试
0046    if (2 > argc) { printf("Usage: %s <size of test>\a\a\n", argv[0]);  return 1; }
0047    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0048 #if defined(DSA_DEPQ_SMMH)
0049    test(atoi(argv[1])); //元素类型可在此指定
0050 #else
0051    printf("PQ type not defined yet\n");
0052 #endif
0053    return 0;
0054 }