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