0001 /******************************************************************************************
0002  * Test of Vector
0003  ******************************************************************************************/
0004 #include "vector_test.h"
0005 
0006 int testID = 0; //测试编号
0007 
0008 /******************************************************************************************
0009  * 测试：无序向量的（顺序）查找
0010  ******************************************************************************************/
0011 template <typename T> void TestFind( Vector<T>& V ) {
0012    for ( Rank i = 0; i < V.size(); i++ ) { //依次查找向量中元素，当然成功
0013       T e =  V[i]; print ( e );
0014       Rank r = V.find ( e );
0015       if ( -1 != r ) printf ( " : found at V[%d] = %d", r, V[r] );
0016       else printf ( " : not found until V[%d] <> %d", r, e );
0017       printf ( "\n" );
0018    }
0019    for ( Rank i = 0; i <= V.size(); i++ ) { //依次查找每对相邻元素的均值，可能成功
0020       T a = ( 0 < i ) ? V[i - 1] : V[0] - 4;
0021       T b = ( i < V.size() ) ? V[i] : V[V.size()-1] + 4;
0022       T e =  ( a + b ) / 2; print ( e );
0023       Rank r = V.find ( e );
0024       if ( -1 != r ) printf ( " : found at V[%d] = %d", r, V[r] );
0025       else printf ( " : not found until V[%d] <> %d", r, e );
0026       printf ( "\n" );
0027    }
0028 }
0029 
0030 /******************************************************************************************
0031  * 测试：有序向量的查找（binSearch或fibSearch）
0032  ******************************************************************************************/
0033 template <typename T> void TestSearch( Vector<T>& V ) {
0034    for ( Rank i = 0; i < V.size(); i++ ) { //依次查找向量中元素，当然成功
0035       T e =  V[i]; print ( e ); printf(": by ");
0036       Rank r = V.search ( e );
0037       if ( V[r] == e ) printf ( "found at V[%d] = %d", r, V[r] );
0038       else printf ( "found at V[%d] = %d <> %d\a\a", r, V[r], e );
0039       printf ( "\n\n" );
0040    }
0041    for ( Rank i = 0; i <= V.size(); i++ ) { //依次相邻元素的均值，可能成功
0042       T a = ( 0 < i ) ? V[i - 1] : V[0] - 4;
0043       T b = ( i < V.size() ) ? V[i] : V[V.size()-1] + 4;
0044       T e =  ( a + b ) / 2; print ( e ); printf(": by ");
0045       Rank r = V.search ( e );
0046       printf ( "V[%3d] =", r ); ( -1 == r ) ? print ( "-INF" ) : print ( V[r] ); printf ( "  ~  " );
0047       printf ( "V[%3d] =", r + 1 ); ( r + 1 < V.size() ) ? print ( V[r + 1] ) : print ( "+INF" );
0048       bool ordered = true;
0049       if ( ( -1 != r  ) && ( V[r] > e ) ) ordered = false;
0050       if ( ( r + 1 < V.size() ) && ( V[r + 1] <= e ) ) ordered = false;
0051       if ( !ordered ) printf ( "\tincorrect search\a\a" );
0052       printf ( "\n\n" );
0053    }
0054 }
0055 
0056 /******************************************************************************************
0057  * 测试：有序向量的插入
0058  ******************************************************************************************/
0059 template <typename T> //元素类型
0060 void TestOrderedInsertion( Vector<T>& V, Rank n ) {
0061    while ( n * 2 > V.size() ) {
0062       T e = dice ( ( T ) n * 2 );
0063       printf ( "Inserting " ); print ( e ); printf ( " by " );
0064       V.insert ( V.search ( e ) + 1, e );
0065       print ( V );
0066    }
0067 }
0068 
0069 /******************************************************************************************
0070  * 测试向量
0071  ******************************************************************************************/
0072 template <typename T> //元素类型
0073 void testVector( Rank testSize ) {
0074    printf ( "\n  ==== Test %2d. Generate a random vector\n", testID++ );
0075    Vector<T> V;
0076    for ( Rank i = 0; i < testSize; i++ ) //在[0,3n)中随机选择n个数
0077       V.insert ( dice ( i + 1 ), dice ( ( T ) testSize * 3 ) );
0078    PRINT ( V );
0079 //
0080    printf ( "\n  ==== Test %2d. Sort by selection\n", testID++ );
0081    Vector<T> S(testSize);
0082    for ( Rank k = 0; k < testSize; k++ )
0083       S.insert( V[V.select( k )] ); //将第k大的元素放到[k]
0084    PRINT( S );
0085 //
0086    printf ( "\n  ==== Test %2d. unsort\n", testID++ );
0087    V.unsort(); PRINT ( V );
0088 //
0089    printf ( "\n  ==== Test %2d. Lowpass on\n", testID++ ); PRINT ( V );
0090    int i = V.size(); while ( 0 < --i ) { V[i-1] *= 7; V[i-1] += V[i]; V[i-1] >>= 3; }    PRINT ( V );
0091 //
0092    printf ( "\n  ==== Test %2d. Increase\n", testID++ ); PRINT ( V );
0093    increase ( V ); PRINT ( V );
0094 //
0095    printf ( "\n  ==== Test %2d. FIND in\n", testID++ ); PRINT ( V );
0096    TestFind<T> ( V );
0097 //
0098    printf ( "\n  ==== Test %2d. Sort degenerate intervals each of size 1 in\n", testID++ ); PRINT ( V );
0099    for ( Rank i = 0; i < V.size(); i += V.size() / 5 ) { V.sort ( i, i+1 ); PRINT ( V ); } //element by element
0100    Rank trunk = int(ceil(V.size()/5.0));
0101 //
0102    printf ( "\n  ==== Test %2d. Sort %d intervals each of size <=%d in\n", testID++, V.size()/trunk, trunk ); PRINT ( V );
0103    for ( Rank i = 0; i < V.size(); i += trunk ) { printf("[%d , %d)\n", i, min ( V.size(), i + trunk ) ); V.sort ( i, min ( V.size(), i + trunk ) ); PRINT ( V ); } //interval by interval
0104 //
0105    printf ( "\n  ==== Test %2d. Sort the entire vector of\n", testID++ ); PRINT ( V );
0106    V.sort(); PRINT ( V );
0107 //
0108    printf ( "\n  ==== Test %2d. FIND in\n", testID++ ); PRINT ( V );
0109    TestFind<T> ( V );
0110 //
0111    printf ( "\n  ==== Test %2d. SEARCH in\n", testID++ ); PRINT ( V );
0112    TestSearch<T> ( V );
0113 //
0114    printf ( "\n  ==== Test %2d. Unsort interval [%d, %d) in\n", testID++, V.size() / 4, 3 * V.size() / 4 ); PRINT ( V );
0115    V.unsort ( V.size() / 4, 3 * V.size() / 4 ); PRINT ( V );
0116 //
0117    printf ( "\n  ==== Test %2d. Unsort interval [%d, %d) in\n", testID++, 0, V.size() ); PRINT ( V );
0118    V.unsort(); PRINT ( V );
0119 //
0120    printf ( "\n  ==== Test %2d. Copy interval [%d, %d) from\n", testID++, V.size() / 4, 3 * V.size() / 4 ); PRINT ( V );
0121    Vector<T> U ( V, V.size() / 4, 3 * V.size() / 4 ); PRINT ( U );
0122 //
0123    printf ( "\n  ==== Test %2d. Copy from\n", testID++ ); PRINT ( V );
0124    Vector<T> W ( V ); PRINT ( W );
0125 //
0126    printf ( "\n  ==== Test %2d. Clone from\n", testID++ ); PRINT ( U );
0127    W = U; PRINT ( W );
0128 //
0129    printf ( "\n  ==== Test %2d. Remove redundancy in unsorted\n", testID++ ); PRINT ( V );
0130    printf ( "%d node(s) removed\n", V.dedup() ); PRINT ( V );
0131 //
0132    printf ( "\n  ==== Test %2d. Sort the entire vercot of\n", testID++ ); PRINT ( V );
0133    V.sort(); PRINT ( V );
0134 //
0135    printf ( "\n  ==== Test %2d. Remove redundancy in sorted\n", testID++ ); PRINT ( V );
0136    printf ( "%d node(s) removed\n", V.uniquify() ); PRINT ( V );
0137 //
0138    printf ( "\n  ==== Test %2d. FIND in\n", testID++ ); PRINT ( V );
0139    TestFind<T> ( V );
0140 //
0141    printf ( "\n  ==== Test %2d. SEARCH & INSERT in\n", testID++ ); PRINT ( V );
0142    TestOrderedInsertion<T> ( V, testSize );  PRINT ( V );
0143 //
0144    printf ( "\n  ==== Test %2d. Remove redundancy in sorted\n", testID++ ); PRINT ( V );
0145    printf ( "%d node(s) removed\n", V.uniquify() ); PRINT ( V );
0146 }
0147 
0148 /******************************************************************************************
0149  * 测试向量
0150  ******************************************************************************************/
0151 int main( int argc, char* argv[] ) {
0152    if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; }
0153    srand((unsigned int)time(NULL)); //随机种子
0154    //srand( 31415926 ); //固定种子（假种子，调试用）
0155    testVector<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择
0156    return 0;
0157 }