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++ ) V.insert ( dice ( i + 1 ), dice ( ( T ) testSize * 3 ) ); //在[0, 3n)中选择n个数，随机插入向量
0077    PRINT ( V );
0078    printf ( "\n  ==== Test %2d. Selection\n", testID++ );
0079    Vector<T> S;
0080    for ( Rank k = 0; k < testSize; k++ )
0081       S.insert( V[V.select( k )] );
0082    printf( "Sorted by %d selection(s)\n", testSize ); PRINT( S ); PRINT ( V );
0083    printf ( "\n  ==== Test %2d. unsort\n", testID++ );
0084    V.unsort(); PRINT ( V );
0085    printf ( "\n  ==== Test %2d. Lowpass on\n", testID++ ); PRINT ( V );
0086    int i = V.size(); while ( 0 < --i ) { V[i-1] *= 7; V[i-1] += V[i]; V[i-1] >>= 3; }    PRINT ( V );
0087    printf ( "\n  ==== Test %2d. Increase\n", testID++ ); PRINT ( V );
0088    increase ( V ); PRINT ( V );
0089    printf ( "\n  ==== Test %2d. FIND in\n", testID++ ); PRINT ( V );
0090    TestFind<T> ( V );
0091    printf ( "\n  ==== Test %2d. Sort degenerate intervals each of size 1 in\n", testID++ ); PRINT ( V );
0092    for ( Rank i = 0; i < V.size(); i += V.size() / 5 ) { V.sort ( i, i+1 ); PRINT ( V ); } //element by element
0093    Rank trunk = int(ceil(V.size()/5.0));
0094    printf ( "\n  ==== Test %2d. Sort %d intervals each of size <=%d in\n", testID++, V.size()/trunk, trunk ); PRINT ( V );
0095    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
0096    printf ( "\n  ==== Test %2d. Sort the entire vector of\n", testID++ ); PRINT ( V );
0097    V.sort();   PRINT ( V );
0098    printf ( "\n  ==== Test %2d. FIND in\n", testID++ ); PRINT ( V );
0099    TestFind<T> ( V );
0100    printf ( "\n  ==== Test %2d. SEARCH in\n", testID++ ); PRINT ( V );
0101    TestSearch<T> ( V );
0102    printf ( "\n  ==== Test %2d. Unsort interval [%d, %d) in\n", testID++, V.size() / 4, 3 * V.size() / 4 ); PRINT ( V );
0103    V.unsort ( V.size() / 4, 3 * V.size() / 4 );   PRINT ( V );
0104    printf ( "\n  ==== Test %2d. Unsort interval [%d, %d) in\n", testID++, 0, V.size() ); PRINT ( V );
0105    V.unsort();   PRINT ( V );
0106    printf ( "\n  ==== Test %2d. Copy interval [%d, %d) from\n", testID++, V.size() / 4, 3 * V.size() / 4 ); PRINT ( V );
0107    Vector<T> U ( V, V.size() / 4, 3 * V.size() / 4 );
0108    PRINT ( U );
0109    printf ( "\n  ==== Test %2d. Copy from\n", testID++ ); PRINT ( V );
0110    Vector<T> W ( V );
0111    PRINT ( W );
0112    printf ( "\n  ==== Test %2d. Clone from\n", testID++ ); PRINT ( U );
0113    W = U;
0114    PRINT ( W );
0115    printf ( "\n  ==== Test %2d. Remove redundancy in unsorted\n", testID++ ); PRINT ( V );
0116    printf ( "%d node(s) removed\n", V.dedup() );   PRINT ( V );
0117    printf ( "\n  ==== Test %2d. Sort the entire vercot of\n", testID++ ); PRINT ( V );
0118    V.sort();   PRINT ( V );
0119    printf ( "\n  ==== Test %2d. Remove redundancy in sorted\n", testID++ ); PRINT ( V );
0120    printf ( "%d node(s) removed\n", V.uniquify() );   PRINT ( V );
0121    printf ( "\n  ==== Test %2d. FIND in\n", testID++ ); PRINT ( V );
0122    TestFind<T> ( V );
0123    printf ( "\n  ==== Test %2d. SEARCH & INSERT in\n", testID++ ); PRINT ( V );
0124    TestOrderedInsertion<T> ( V, testSize );  PRINT ( V );
0125    printf ( "\n  ==== Test %2d. Remove redundancy in sorted\n", testID++ ); PRINT ( V );
0126    printf ( "%d node(s) removed\n", V.uniquify() );   PRINT ( V );
0127 }
0128 
0129 /******************************************************************************************
0130  * 测试向量
0131  ******************************************************************************************/
0132 int main( int argc, char* argv[] ) {
0133    if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; }
0134    srand((unsigned int)time(NULL)); //随机种子
0135    //srand( 31415926 ); //固定种子（假种子，调试用）
0136    testVector<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择
0137    return 0;
0138 }