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