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