教学班级及项目地址

• 教学班级：周四班
• 项目地址：https://github.com/seeeagull/Word_Chain

PSP表格-预期

在开始实现程序之前，在下述 PSP 表格记录下你估计将在程序的 各个模块的开发上耗费的时间。

设计理念

看教科书和其它资料中关于 Information Hiding，Interface Design，Loose Coupling 的章节，说明你们在结对编程中是如何利用这些方法对接口进行设计的。

• 信息隐藏(Infromation Hiding)： 指模块中包含的信息(算法和数据)不被不需要这些信息的其他模块访问。模块间只交流实现软件功能所必需的信息。根据信息隐藏原则，在概要设计时就列出将来可能发生变化的因素，并在模块划分时将这些因素放到个别模块的内部。这样，在将来由于这些因素变化而需修改软件时，只需修改这些个别的模块即可，其它模块不受影响。

  我们依照此原则设计了负责文件读入和输出的FileIO模块、负责实现具体图算法的graph模块、负责解析命令行参数的controller模块。将实现细节隐藏在模块内部，外部只保留调用接口，即保证用户无法直接修改数据，提高了程序的安全性，还便于程序的修改和维护。

• 接口设计(Interface Design)：

  我们的接口设计遵循单一职责原则（每个实体只有一个引起变化的原因）、迪米特法则（一个对象应对其它对象保持最少的了解，只要知道如何调用其它对象的公共接口即可）。
  除此之外，我们在文档中规定了各种可能出现的异常以及相应处理。
  在命名方面，我们遵守 google c++ 命名规范 https://google.github.io/styleguide/cppguide.html。

• 松耦合(loose coupling)： 松耦合的多个模块之间依赖性较低，因而进行修改时的代价较小。

  如“信息隐藏”部分所述，我们的多个模块均为松耦合，更新修改代价较小，便于更换模块。

计算模块接口的设计与实现过程

设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？说明你的算法的关键（不必列出源代码），以及独到之处。

我们的计算模块接口设计如下：

int gen_chains_all(char* words[], int len, char* result[]);
int gen_chain_word(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);
int gen_chain_char(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);

• gen_chains_all 函数对应功能性参数 -n ，获取所有单词链。
  • words 为输入的单词列表。要求已经转换为全小写，但不要求去重。
  • len 为输入单词列表的长度。
  • result 存放计算得到的全部单词链。
  • 函数返回值为单词链个数。
• gen_chain_word 函数对应功能性参数 -w ，获取单词个数最多的单词链。
  • 前三个参数意义同上。
  • head 对应附加参数 -h ，为指定的开头字母，若为 0 则表示无指定开头字母。
  • tail 对应附加参数 -t ，为指定的结尾字母，若为 0 则表示无指定结尾字母。
  • reject 对应附加参数 -j ，为指定的禁止开头字母，若为 0 则表示无指定的禁止开头字母。
  • enable_loop 对应附加参数 -r ，表示是否允许有环。
  • 函数返回值为最长单词链的单词个数。
• gen_chain_char 函数对应功能性参数 -c ，获取字母个数最多的单词链。
  • 七个参数意义同上。
  • 函数返回值为最长单词链的字母个数。

计算模块主要由以下文件构成：

• core.h core.cpp：接口的声明和定义。
• controller.h controller.cpp：定义 Controller 类，负责命令行参数的解析。
• file_io.h file_io.cpp：定义 FileIo 类，负责文件的输入和输出。
• graph.h graph.cpp：定义 Graph 类，负责图算法内部实现。
• types.h：定义异常码、异常类型等。
  每个类内部的函数即关联关系详见下文 UML 图。

计算流程如下：
首先读入单词列表，去重，调用 Graph 类的 AddWord 方法建图。每个小写字母为一个节点，单词为一条从首字母指向尾字母的边。

1. 若调用接口 gen_chains_all，则调用 Graph 类的 FindAllWordChains 函数。
   具体算法为先按照拓扑倒序 dp 求出总单词链数。然后 dfs 输出所有链。

2. 若调用接口 gen_chain_word 或 gen_chain_word ，则首先检查和设置功能参数，调用 Graph 类的 DetectLoop 方法检测有无环。判断环的算法为 Tarjan，同时可以得到拓扑序，特别地，对于自环情况需要特别处理，只有当一个点有多于一个自环的时候算作有环。然后调用 Graph 类的 FindLongestChain 方法：其中 gen_chain_word 对应参数 weighted = false；gen_chain_word 对应参数 weighted = true。
   根据有无环选择调用 FindLongestChainWithLoops 方法或者 FindLongestChainWithoutLoops 方法。
   对于无环的情况，则按照拓扑倒序 dp。并且由于规定单词链必须至少由两个单词组成，所以在 dp 之后要枚举所有边作为第一条边的情况，取能得到的最长链为答案。
   对于有环的情况，使用状压 dp 求解。状态只需要记录在一个连通块内经过的边，跨越连通块时将状态清零。并且由于最多只有 100 条边，所以可以用两个 long long int 表示所有状态，进行记忆化搜索。与无环情况相同，在搜索一遍后要枚举所有边作为第一条边的情况，取能得到的最长链为答案。

开发环境下编译通过无警告

UML图

阅读有关 UML 的内容，画出 UML 图显示计算模块部分各个实体之间的关系（画一个图即可）https://en.wikipedia.org/wiki/Unified_Modeling_Language

计算模块接口部分的性能改进

记录在改进计算模块性能上所花费的时间，并展示你程序中消耗最大的函数，陈述你的性能改进策略。

对于无环的情况，已经可以做到线性复杂度，所以无需进一步优化。
对于有环的情况，是一个 NP 问题，为保证正确性不能采用近似算法。可以在一些细节处优化，但复杂度无法降低：首先将重边排序，优先走最长边；存在自环则一定先走自环，不需要尝试；状态只需要保存同一个连通块内走过的边，跨连通块时清零。若图为完全有向图时算法跑满最多情况（而且内存会炸），经实验，当点数为 5 时时间尚较短，而到 6 时已无法接受。不过对于随机样例，普遍表现还是可以让人接受的。
构造一个 5 个点的完全有向图（每个点带自环），性能分析如下：

可以看到主要性能瓶颈在于 DfsLongestChain 方法，而这是符合预期的。

关于Design by Contract / Code Contract的思考

阅读 Design by Contract，Code Contract 的内容，并描述这些做法的优缺点，说明你是如何把它们融入结对作业中的。

• http://en.wikipedia.org/wiki/Design_by_contract
• http://msdn.microsoft.com/en-us/devlabs/dd491992.aspx

契约式设计是一种设计计算机软件的方法。这种方法要求软件设计者为软件组件定义正式的，精确的并且可验证的接口，这样，为传统的抽象数据类型又增加了先验条件、后验条件和不变式。

在我们的设计中，契约式编程的思想体现在我们在 Controller 里解析命令行传入参数并做异常处理的过程。我们设计了一套异常和对应的异常码，内层函数遇到异常情况会抛出对应异常，而最外层调用方 Controller 根据 catch 的异常返回对应异常码。Gui 调用接口时可以根据得到的异常码做相应相应，从而提供更好的用户使用体验。

单元测试

计算模块部分单元测试展示。***展示出项目部分单元测试代码，并说明测试的函数，构造测试数据的思路。并***将单元测试得到的测试覆盖率截图，发表在博客中。要求总体覆盖率到 90% 以上，否则单元测试部分视作无效。

测试使用了 1.12.1 版本的 gtest，分为正确性测试、鲁棒性测试两部分。我们共构造有不同特征的 12 个 testcase.txt，21 种测试参数组合，分别针对合法参数、非法参数、有环场景来设计正确性测试。对于鲁棒性测试，我们共设计了 12 种异常，48 组测试参数进行测试。

我们的 core.dll 调用的所有代码被包含在 ./compute 路径下，因此可以用该文件夹下的覆盖率表示该接口的单元测试覆盖率。我们使用 clion 整合的 gcov 进行测试覆盖率分析，行覆盖率达到 97%，分支覆盖率达到了 93%。

正确性测试

正确性参数见上表测试参数一列。部分 testcase 代码如下。

TEST(correctness_test, testcase1) {const char *file_name = "../testcase/testcase1.txt";const char *argv[] = {"Wordlist.exe", "-n", file_name};WordChain word_chain((std::string(file_name)));word_chain.BuildGraph();int std_res = word_chain.GetChainCnt();word_chain.OutputFile("../output/output1_std.txt");int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../output/output1.txt");EXPECT_EQ(ret, 0);EXPECT_EQ(res, std_res);
}TEST(correctness_test, testcase2_1) {const char *file_name = "../testcase/testcase2.txt";const char *argv[] = {"Wordlist.exe", "-r", "-h", "c", "-j", "v", "-w", file_name};WordChain word_chain((std::string(file_name)));word_chain.BuildGraph();int std_res = word_chain.GetMostWordChain('c', '0', 'v');word_chain.OutputFile("../output/output2_1_std.txt");int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res,"../output/output2_1.txt");EXPECT_EQ(ret, 0);EXPECT_EQ(res, std_res);
}TEST(correctness_test, testcase2_2) {const char *file_name = "../testcase/testcase2.txt";const char *argv[] = {"Wordlist.exe", "-r", "-j", "h", "-t", "j", "-c", file_name};WordChain word_chain((std::string(file_name)));word_chain.BuildGraph();int std_res = word_chain.GetMostCharChain('0', 'j', 'h');word_chain.OutputFile("../output/output2_2_std.txt");int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res,"../output/output2_2.txt");EXPECT_EQ(ret, 0);EXPECT_EQ(res, std_res);
}

鲁棒性测试

见下文异常处理部分。

异常处理

我们共支持了以下 12 种异常，每一种异常都进行了充分的单元测试。

对应的 testcase 代码如下。

TEST(robustness_test, testcase1) {const char *argv[] = {"Wordlist.exe", "-n"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp1.txt");EXPECT_EQ(ret, kNoFilePath);
}TEST(robustness_test, testcase2_1) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase2.txt", "../testcase/testcase2.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp2_1.txt");EXPECT_EQ(ret, kMultiFilePath);
}TEST(robustness_test, testcase2_2) {const char *argv[] = {"Wordlist.exe", "-w", "../testcase/testcase2.txt", "../testcase/testcase2.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp2_2.txt");EXPECT_EQ(ret, kMultiFilePath);
}TEST(robustness_test, testcase2_3) {const char *argv[] = {"Wordlist.exe", "-c", "../testcase/testcase2.txt", "../testcase/testcase2.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp2_3.txt");EXPECT_EQ(ret, kMultiFilePath);
}TEST(robustness_test, testcase3_1) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase0.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp3_1.txt");EXPECT_EQ(ret, kFileNotExists);
}TEST(robustness_test, testcase3_2) {const char *argv[] = {"Wordlist.exe", "-w", "../testcase/testcase0.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp3_2.txt");EXPECT_EQ(ret, kFileNotExists);
}TEST(robustness_test, testcase3_3) {const char *argv[] = {"Wordlist.exe", "-c", "../testcase/testcase0.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp3_3.txt");EXPECT_EQ(ret, kFileNotExists);
}TEST(robustness_test, testcase4_1) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase11.c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp4_1.txt");EXPECT_EQ(ret, kFileTypeError);
}TEST(robustness_test, testcase4_2) {const char *argv[] = {"Wordlist.exe", "-w", "../testcase/testcase11.c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp4_2.txt");EXPECT_EQ(ret, kFileTypeError);
}TEST(robustness_test, testcase4_3) {const char *argv[] = {"Wordlist.exe", "-c", "../testcase/testcase11.c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp4_3.txt");EXPECT_EQ(ret, kFileTypeError);
}TEST(robustness_test, testcase4_4) {const char *argv[] = {"Wordlist.exe", "-n", "t.c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp4_4.txt");EXPECT_EQ(ret, kFileTypeError);
}TEST(robustness_test, testcase4_5) {const char *argv[] = {"Wordlist.exe", "-n", "t.c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp4_5.txt");EXPECT_EQ(ret, kFileTypeError);
}TEST(robustness_test, testcase4_6) {const char *argv[] = {"Wordlist.exe", "-n", "t.c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp4_6.txt");EXPECT_EQ(ret, kFileTypeError);
}TEST(robustness_test, testcase5_1) {const char *argv[] = {"Wordlist.exe", "-q", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp5_1.txt");EXPECT_EQ(ret, kIllegalParam);
}TEST(robustness_test, testcase5_2) {const char *argv[] = {"Wordlist.exe", "-r", "a", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp5_2.txt");EXPECT_EQ(ret, kIllegalParam);
}TEST(robustness_test, testcase5_3) {const char *argv[] = {"Wordlist.exe",  "a", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp5_3.txt");EXPECT_EQ(ret, kIllegalParam);
}TEST(robustness_test, testcase6_1) {const char *argv[] = {"Wordlist.exe", "-h", "a", "-t", "s", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp6_1.txt");EXPECT_EQ(ret, kNoFunctionalParam);
}TEST(robustness_test, testcase6_2) {const char *argv[] = {"Wordlist.exe", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp6_2.txt");EXPECT_EQ(ret, kNoFunctionalParam);
}TEST(robustness_test, testcase6_3) {const char *argv[] = {"Wordlist.exe", "-h", "a", "-j", "s", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp6_3.txt");EXPECT_EQ(ret, kNoFunctionalParam);
}TEST(robustness_test, testcase7_1) {const char *argv[] = {"Wordlist.exe", "-w", "../testcase/testcase1.txt", "-n"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_1.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_2) {const char *argv[] = {"Wordlist.exe", "-c", "../testcase/testcase1.txt", "-n"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_2.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_3) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase1.txt", "-w"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_3.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_4) {const char *argv[] = {"Wordlist.exe", "-c", "../testcase/testcase1.txt", "-w"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_4.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_5) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase1.txt", "-c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_5.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_6) {const char *argv[] = {"Wordlist.exe", "-w", "../testcase/testcase1.txt", "-c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_6.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_7) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase1.txt", "-h", "h"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_7.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_8) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase1.txt", "-t", "h"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_8.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase7_9) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase1.txt", "-j", "h"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp7_9.txt");EXPECT_EQ(ret, kParamsConflict);
}TEST(robustness_test, testcase8_1) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase1.txt", "-n"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp8_1.txt");EXPECT_EQ(ret, kDuplicateParam);
}TEST(robustness_test, testcase8_2) {const char *argv[] = {"Wordlist.exe", "-w", "../testcase/testcase1.txt", "-w"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp8_2.txt");EXPECT_EQ(ret, kDuplicateParam);
}TEST(robustness_test, testcase8_3) {const char *argv[] = {"Wordlist.exe", "-c", "../testcase/testcase1.txt", "-c"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp8_3.txt");EXPECT_EQ(ret, kDuplicateParam);
}TEST(robustness_test, testcase9_1) {const char *argv[] = {"Wordlist.exe", "-h", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp9_1.txt");EXPECT_EQ(ret, kCharNotAssign);
}TEST(robustness_test, testcase9_2) {const char *argv[] = {"Wordlist.exe", "-t", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp9_2.txt");EXPECT_EQ(ret, kCharNotAssign);
}TEST(robustness_test, testcase9_3) {const char *argv[] = {"Wordlist.exe", "-j", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp9_3.txt");EXPECT_EQ(ret, kCharNotAssign);
}TEST(robustness_test, testcase10_1) {const char *argv[] = {"Wordlist.exe", "-h", "AB", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_1.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_2) {const char *argv[] = {"Wordlist.exe", "-t", "AB", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_2.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_3) {const char *argv[] = {"Wordlist.exe", "-j", "AB", "-n", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_3.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_4) {const char *argv[] = {"Wordlist.exe", "-h", "1", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_4.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_5) {const char *argv[] = {"Wordlist.exe", "-t", "1", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_5.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_6) {const char *argv[] = {"Wordlist.exe", "-j", "1", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_6.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_7) {const char *argv[] = {"Wordlist.exe", "-h", "a", "a", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_7.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_8) {const char *argv[] = {"Wordlist.exe", "-t", "a", "a", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_8.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase10_9) {const char *argv[] = {"Wordlist.exe", "-j", "a", "a", "../testcase/testcase1.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp10_9.txt");EXPECT_EQ(ret, kIllegalChar);
}TEST(robustness_test, testcase11_1) {const char *argv[] = {"Wordlist.exe", "-n", "../testcase/testcase5.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp11_1.txt");EXPECT_EQ(ret, kUnexpectedLoop);
}TEST(robustness_test, testcase11_2) {const char *argv[] = {"Wordlist.exe", "-w", "../testcase/testcase5.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp11_2.txt");EXPECT_EQ(ret, kUnexpectedLoop);
}TEST(robustness_test, testcase11_3) {const char *argv[] = {"Wordlist.exe", "-c", "../testcase/testcase5.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp11_3.txt");EXPECT_EQ(ret, kUnexpectedLoop);
}TEST(robustness_test, testcase12_1) {const char *argv[] = {"Wordlist.exe", "-r", "-w", "../testcase/testcase13.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp12_1.txt");EXPECT_EQ(ret, kLengthOverflow);
}TEST(robustness_test, testcase12_2) {const char *argv[] = {"Wordlist.exe", "-r", "-c", "../testcase/testcase13.txt"};Controller controller{};int res;int ret = controller.Cmd(sizeof(argv) / sizeof(argv[0]), const_cast(argv), &res, "../exp12_2.txt");EXPECT_EQ(ret, kLengthOverflow);
}

UI设计

界面模块使用 Qt5 实现。

紧 跟 时 事：【我放弃了C+±哔哩哔哩】 https://b23.tv/LIkHegh 。

整体效果如下：

• macos 运行实例（直接调用函数）

• windows 运行实例（链接 core.dll）

UI布局及使用流程

UI分成两个部分。上侧用于选择目标功能、进行限制、点击求解、导入待处理txt文件、保存求解结果；下侧分成两部分，左侧用于展示待处理文本，右侧用于展示求解结果。用户使用流程为：

1. 点击“导入”导入txt文件，或者在左侧手动输入待处理数据。待处理数据可以包括非英文字符，按照单词的定义为：被非英文字符间隔的连续英文字符序列处理
2. 选择上方功能性参数和中间辅助性参数
3. 点击求解，求解结果将显示在右下方窗口
4. 如需保存求解结果，点击“导出”并在弹出窗口中设置保存文件路径及文件名

UI部分实现

UI层面添加约束解决异常

对异常的处理通常有两种：1. UI进行较少的限制，用户触发异常提示用户重新输入 或2. UI直接进行约束

对大部分异常(expcode = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)，我们采用了第二种方式添加约束保证用户无法触发；对于需要根据是否形成环路判断的异常(expcode = 11)和需要根据结果数组长度判定的异常(expcode = 12)则采用第一种方式在用户触发异常后提示用户。对各异常的实现如下：

// expcode=1，参数中没有文件，求解按钮点击后从inputContentTextEdit处读取文件，如果为空则按空文件处理
std::string inputContent = inputContentTextEdit->toPlainText().toStdString();
// expcode=2，参数中多个文件，每次点击导入按钮后将txt文件内容映射到inputContentTextEdit
// expcode=3，参数中文件不存在，点击导入按钮后使用QFileDialog::getOpenFileName弹出对话框筛选文件，无法选择不存在文件
// expcode=4，参数中文件不是txt文件，设置QFileDialog::getOpenFileName的filter参数为"文本文件(*.txt)"，限定选择文件只能是txt文件
QString inputPath = QFileDialog::getOpenFileName(this, dlgTitle, curPath, filter);if (!inputPath.isEmpty()) {QFile inputFile(inputPath);if (!inputFile.open(QIODevice::ReadOnly | QIODevice::Text)) return;QTextStream inputContentTextStream(&inputFile);QString line = inputContentTextStream.readLine();QString inputContent;while (!line.isNull()) {inputContent.append(line);line = inputContentTextStream.readLine();}inputPathLineEdit->setText(inputPath);inputContentTextEdit->setText(inputContent);}
// expcode=5，非法参数，只有控制面板的参数可以选择
// expcode=6，无功能性参数，默认选择-w
functionalParamsRadio[1]->setChecked(true);
// expcode=7，参数冲突，功能性参数使用radioButton组，只能选择一个
functionalParamsGroup = new QButtonGroup;for (int i = 0; i < NumFunctions; ++i) {functionalParamsRadio[i] = new QRadioButton(functions[i]);functionalParamsGroup->addButton(functionalParamsRadio[i]);layout->addWidget(functionalParamsRadio[i], 0, 4 * i, 1, 4);}
// expcode=7，-n不能同时选择-h -t -j -r，设置选择-n时无法选择这四个参数
todo
// expcode=8，多次指定相同参数，UI只有选择与不选择两个状态，没有选择次数
// expcode=9，-h -t -j参数没有接字符串，保证这三个参数后面的选择框要么不选表示未指定，要么输入一个英文字母
// expcode=10，-h -t -j参数接的字符串不合法，通过Regex限定输入字符一定为英文字母
limitChar[i]->setPlaceholderText("允许所有");QRegularExpression regex("[a-zA-Z]{1}");QValidator *validator = new QRegularExpressionValidator(regex);limitChar[i]->setValidator(validator);
// expcode=11，未指定-r但出现环，求解出现环后弹出对话框提示用户
// expcode=12，输出单词数超过20000，求解输出单词过多弹出对话框提示用户
if (ret < 0) {if (ret == -kUnexpectedLoop) {QMessageBox::information(nullptr, "提示", "输入存在环，请勾选\"允许出现环\"");} else if (ret == -kLengthOverflow) {QMessageBox::information(nullptr, "提示", "输出单词链过长");}return;}

UI信号控制事件实现

void WordChainUI::onInputPathChooseButtonClicked() {QString curPath = QDir::currentPath();QString dlgTitle = "选择待导入文件";QString filter = "文本文件(*.txt)";QString inputPath = QFileDialog::getOpenFileName(this, dlgTitle, curPath, filter);if (!inputPath.isEmpty()) {QFile inputFile(inputPath);if (!inputFile.open(QIODevice::ReadOnly | QIODevice::Text)) return;QTextStream inputContentTextStream(&inputFile);QString line = inputContentTextStream.readLine();QString inputContent;while (!line.isNull()) {inputContent.append(line);line = inputContentTextStream.readLine();}inputPathLineEdit->setText(inputPath);inputContentTextEdit->setText(inputContent);}
}void WordChainUI::onSolveButtonClicked() {char functionalParam = functionalParamsRadio[0]->isChecked() ? 'n' :functionalParamsRadio[1]->isChecked() ? 'w' :functionalParamsRadio[2]->isChecked() ? 'c' : 0;char head = limitChar[0]->text().toStdString().length() > 0 ? tolower(limitChar[0]->text().toStdString()[0]) : 0;char tail = limitChar[1]->text().toStdString().length() > 0 ? tolower(limitChar[1]->text().toStdString()[0]) : 0;char reject = limitChar[2]->text().toStdString().length() > 0 ? tolower(limitChar[2]->text().toStdString()[0]) : 0;bool enable_loop = allowRingsRadio->isChecked();char *words[200000];char *res[20000];std::string inputContent = inputContentTextEdit->toPlainText().toStdString();std::string s;int len = 0;for (int i = 0; i < inputContent.length(); ++i) {char c = inputContent[i];if (isupper(c)) s += (char) tolower(c);else if (islower(c)) s += c;else {if (s.length() > 0) {words[len] = new char[s.length() + 1];for (int j = 0; j < s.length(); ++j) {words[len][j] = s[j];}words[len++][s.length()] = '\0';s = "";}}}QElapsedTimer timer;timer.start();int ret;switch (functionalParam) {case 'n':ret = gen_chains_all(words, len, res);break;case 'w':ret = gen_chain_word(words, len, res, head, tail, reject, enable_loop);break;case 'c':ret = gen_chain_char(words, len, res, head, tail, reject, enable_loop);break;default:// never hit hereret = -1;break;}qint64 elapsed = timer.nsecsElapsed();if (ret < 0) {if (ret == -kUnexpectedLoop) {QMessageBox::information(nullptr, "提示", "输入存在环，请勾选\"允许出现环\"");} else if (ret == -kLengthOverflow) {QMessageBox::information(nullptr, "提示", "输出单词链过长");}return;}std::string usedTimePrompt = "用时: " + std::to_string(abs(elapsed / 1000)) + "秒";QString usedTimePromptQ = QString::fromStdString(usedTimePrompt);usedTimeLabel->setText(usedTimePromptQ);QStringList strList;int i = 0;while (res[i] != nullptr) strList << QString(res[i++]);QString outputContent = strList.join("\n");outputContentTextEdit->setText(outputContent);
}void WordChainUI::onOutputPathChooseButtonClicked() {QString curPath = QDir::currentPath();QString dlgTitle = "保存文件";QString filter = "文本文件(*.txt)";QString outputPath = QFileDialog::getSaveFileName(this, dlgTitle, curPath, filter);if (!outputPath.isEmpty()) {QFile outputFile(outputPath);if (!outputFile.open(QIODevice::ReadWrite)) return;QString outputContent = outputContentTextEdit->toPlainText();outputFile.write(outputContent.toUtf8());outputFile.close();}
}

界面模块与计算模块的对接

详细地描述 UI 模块的设计与两个模块的对接，并在博客中截图实现的功能。

UI设计/布局/使用流程及运行实例截图见上文。

UI和计算模块对接通过onSolveButtonClicked函数中的这部分代码，通过解析功能型参数调用dll的三个接口对计算模块进行调用。调用前后分别使用QElapsedTimer记时，返回结果保存在res数组中，展示在outputContentTextEdit的文本框中。

EXPOSED_FUNCTION int gen_chains_all(char* words[], int len, char* result[]);
EXPOSED_FUNCTION int gen_chain_word(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);
EXPOSED_FUNCTION int gen_chain_char(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);void WordChainUIQt5::onSolveButtonClicked() {char functionalParam = functionalParamsRadio[0]->isChecked() ? 'n' :functionalParamsRadio[1]->isChecked() ? 'w' :functionalParamsRadio[2]->isChecked() ? 'c' : 0;
...QElapsedTimer timer;timer.start();int ret;
switch (functionalParam) {case 'n':ret = gen_chains_all(words, len, res);break;case 'w':ret = gen_chain_word(words, len, res, head, tail, reject, enable_loop);break;case 'c':ret = gen_chain_char(words, len, res, head, tail, reject, enable_loop);break;default:// never hit hereret = -1;break;}
qint64 elapsed = timer.nsecsElapsed();...
}

结对过程

提供两人在讨论的结对图像资料（比如 Live Share 的截图）。关于如何远程进行结对参见作业最后的注意事项。

新主结对纪实：

可以看到我们组的操作系统多样性。队友的 mac 开着文档，我们用我的 windows 远程控制我宿舍的 ubuntu 写代码。
并且值得一提的是：刘佬（gou）只需要从实验室坐个电梯下楼，而我从大运村跋山涉水。

优缺点

看教科书和其它参考书，网站中关于结对编程的章节，例如：http://www.cnblogs.com/xinz/archive/2011/08/07/2130332.html ，说明结对编程的优点和缺点。同时描述结对的每一个人的优点和缺点在哪里（要列出至少三个优点和一个缺点）。

• 结对编程优缺点
  • 优点：可以提高代码质量和开发效率、减少交接工作带来的时间消耗、共同提升水平。
  • 缺点：需要两个人协调时间、工具链、技术栈以及编程风格和习惯。并且开发环境的差异（我有 windows、惯用 ubuntu，他使用 mac）在物理因素限制不能线下同用一台电脑时影响较大。
• jyz优缺点
  • 优点：具有一定算法基础、工程经验、以及 C++ 使用经验，有注重代码风格的良好习惯。
  • 缺点：算法实现不够注意细节。在完全思考好具体实现前常常急于动手。
• ljc优缺点
  • 优点：测试尽心尽责；文档细致详细；态度耐心谦逊。
  • 缺点：开发不跨平台，且无意识哪些部分不跨平台。（具体表现为在 mac 上使用 windows 上在线安装必须换源、离线安装没有二进制编译文件只能从源码构建、编译运行要求 mingw 11.x 和 c++ 17、占内存巨大 的 qt6 开发 gui 模块。）

（P.S. 可以移步 dawning_77 的博客文章看我被挂“三明治法则”花絮。）

PSP表格-实际

附加-模块松耦合

在博客中指明合作小组两位同学的学号，分析两组不同的模块合并之后出现的问题，为何会出现这样的问题，以及是如何根据反馈改进自己模块的。

我们和 19375263 和 20373788 小组的同学互换了 core 模块。虽然他们已经和别的组互换过了，但 ntr 战神一刀一个纯爱人。

由于我们的接口都和作业中给出的建议基本相同，所以没有遇到较大困难，只有具体异常码和 -c 模式下返回值意义不同，在外部做转换即可。

这是我们的 GUI 链接他们的计算模块运行截图：

不过在对拍中被发现了算法实现的各种细节问题……逐一改之。