0001 /******************************************************************************************
0002  * Test of list
0003  ******************************************************************************************/
0004 #include "list_test.h"
0005 
0006 Rank testID = 0; //测试编号
0007 
0008 /******************************************************************************************
0009  * 随机生成长度为n的列表（其中可能包含重复节点）
0010  ******************************************************************************************/
0011 template <typename T> //元素类型
0012 void randomList ( List<T> & list, Rank n ) { //创建长度为n的列表，其元素随机取自[0, 4n)
0013    ListNodePosi<T> p =
0014       ( rand() % 2 )
0015          ? list.insertLast  ( rand() % ( T ) ( n * 4 ) )
0016          : list.insertFirst ( rand() % ( T ) ( n * 4 ) );
0017    for ( Rank i = 1; i < n; i++ )
0018       p = rand() % 2
0019          ? list.insert ( rand() % ( T ) ( n * 4 ), p )
0020          : list.insert ( p, rand() % ( T ) ( n * 4 ) );
0021 }
0022 
0023 /******************************************************************************************
0024  * 测试列表
0025  ******************************************************************************************/
0026 template <typename T> void testList( Rank testSize ) {
0027    printf("\n  ==== Test %2d. Generate a random list with %d elements\n", testID++, testSize);
0028    List<T> L; randomList(L, testSize); PRINT(L);
0029    printf("\n  ==== Test %2d. Sort it\n", testID++);
0030    L.sort(); PRINT(L);
0031 //
0032    printf("\n  ==== Test %2d. Generate two sorted lists each with %d random elements\n", testID++, testSize);
0033    List<T> Lx; randomList(Lx, testSize); PRINT(Lx); Lx.sort(); PRINT(Lx);
0034    List<T> Ly; randomList(Ly, testSize); PRINT(Ly); Ly.sort(); PRINT(Ly);
0035 //
0036    printf("\n  ==== Test %2d. Merge them into a single sorted list\n", testID++);
0037    Lx.merge(Ly); PRINT(Lx); PRINT(Ly);
0038 //
0039    printf ( "\n  ==== Test %2d. Generate two lists each of size %d by random insertions\n", testID++, testSize );
0040    List<T> La; randomList ( La, testSize ); PRINT ( La );
0041    List<T> Lb; randomList ( Lb, testSize ); PRINT ( Lb );
0042 //
0043    printf ( "\n  ==== Test %2d. Call list members by Rank (with high complexity)\n", testID++ );
0044    for ( Rank i = 0; i < La.size(); i++ ) print ( La[i]->data ); printf ( "\n" );
0045    for ( Rank i = 0; i < Lb.size(); i++ ) print ( Lb[i]->data ); printf ( "\n" );
0046 //
0047    printf ( "\n  ==== Test %2d. Concatenation\n", testID++ ); PRINT ( La ); PRINT ( Lb );
0048    while ( 0 < Lb.size() ) La.insertLast ( Lb.remove ( Lb.first() ) ); PRINT ( La ); PRINT ( Lb );
0049 //
0050    printf ( "\n  ==== Test %2d. Increase\n", testID++ ); PRINT ( La );
0051    increase ( La ); PRINT ( La );
0052 //
0053    printf ( "\n  ==== Test %2d. Lowpass (with high complexity) on\n", testID++ ); PRINT ( La );
0054    Rank i = La.size(); while ( 0 < --i ) { La[i-1]->data += La[i]->data; La[i-1]->data >>= 1; } PRINT ( La ); //call-by-rank, clear but slow
0055 //
0056    printf ( "\n  ==== Test %2d. reverse\n", testID++ );
0057    La.reverse(); PRINT ( La );
0058 //
0059    printf ( "\n  ==== Test %2d. Copy all\n", testID++ ); PRINT ( La );
0060    List<T> Le ( La ); PRINT ( Le );
0061    Rank r = dice( La.size() / 4 ), n = dice( La.size() * 3 / 4, La.size() ) - r;
0062 //
0063    printf( "\n  ==== Test %2d. Copy [%d, %d)\n", testID++, r, r + n );
0064    List<T> Ld( La, r, n ); PRINT( Ld );
0065 //
0066    printf ( "\n  ==== Test %2d. Trim by random deletions\n", testID++ ); PRINT ( Ld );
0067    while ( testSize / 4 < Ld.size() ) {
0068       Rank N = dice( Ld.size() ); printf ( "removing L[%d]=", N );
0069       ListNodePosi<T> p = Ld[N]; print ( p->data ); printf ( " ...\n" ); //call-by-rank, clear but slow
0070       Ld.remove ( p ); PRINT ( Ld );
0071    }
0072 //
0073    printf ( "\n  ==== Test %2d. Copy\n", testID++ ); PRINT ( La );
0074    List<T> Lf ( La ); PRINT ( Lf );
0075 //
0076    printf ( "\n  ==== Test %2d. FIND in\n", testID++ ); PRINT ( Lf );
0077    for ( Rank i = 0; i <= testSize * 2; i++ ) { //逐一测试[0, 2n]中的所有可能
0078       ListNodePosi<T> p = Lf.find ( ( T ) i ); printf ( "Looking for " ); print ( ( T ) i ); printf ( ": " );
0079       if ( p ) { printf ( "found with" ); print ( p->data ); }
0080       else printf ( "not found" );
0081       printf ( "\n" );
0082    } //正确的结构应该是大致（n+1次）失败、（n次）成功相间
0083 //
0084    printf ( "\n  ==== Test %2d. Sort\n", testID++ ); PRINT ( La );
0085    La.sort(); PRINT ( La );
0086 //
0087    printf ( "\n  ==== Test %2d. SEARCH in\n", testID++ ); PRINT ( La );
0088    for ( Rank i = 0; i <= testSize * 2; i++ ) { //逐一测试[0, 2n]中的所有可能
0089       ListNodePosi<T> p = La.search ( ( T ) i ); printf ( "Looking for " ); print ( ( T ) i ); printf ( ": " );
0090       printf( ( La.valid( p ) && ( (T)i == p->data ) ) ? "found at" : "failed at" );
0091       La.valid( p ) ? print( p->data ) : print( "head" );
0092       printf ( "\n" );
0093    } //正确的结构应该是大致（n+1次）失败、（n次）成功相间
0094 //
0095    printf ( "\n  ==== Test %2d. Remove redundancy in\n", testID++ ); PRINT ( La );
0096    printf ( "%d node(s) removed\n", La.uniquify() ); PRINT ( La ); La.reverse(); PRINT ( La );
0097 //
0098    printf ( "\n  ==== Test %2d. Remove redundancy in\n", testID++ ); PRINT ( Le );
0099    printf ( "%d node(s) removed\n", Le.dedup() ); PRINT ( Le );
0100 //
0101    printf ( "\n  ==== Test %2d. Sort\n", testID++ ); PRINT ( Le );
0102    Le.sort(); PRINT ( Le );
0103 //
0104    return;
0105 }
0106 
0107 /******************************************************************************************
0108  * 测试列表
0109  ******************************************************************************************/
0110 int main ( int argc, char* argv[] ) {
0111    if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; }
0112    srand( (unsigned int)time( NULL ) ); //随机种子
0113    //srand( 31415926 ); //固定种子（假种子，调试用）
0114    testList<int>( atoi( argv[1] ) ); //元素类型可以在这里任意选择
0115    return 0;
0116 }