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