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