一、三次作业简单介绍
第十三次作业：
实现一个 UML 类图解析器 UmlInteraction
本次作业最终需要实现一个UML类图解析器，可以通过输入各种指令来进行类图有关信息的查询。
实现指令：
| 模型中一共有多少个类 | CLASS_COUNT |
|---|---|
| 类中的操作有多少个 | CLASS_OPERATION_COUNT classname mode |
| 类中的属性有多少个 | CLASS_ATTR_COUNT classname mode |
| 类有几个关联 | CLASS_ASSO_COUNT classname |
| 类的关联的对端是哪些类 | CLASS_ASSO_CLASS_LIST classname |
| 类的操作可见性 | CLASS_OPERATION_VISIBILITY classname methodname |
| 类的属性可见性 | CLASS_ATTR_VISIBILITY classname attrname |
| 类的*父类 | CLASS_TOP_BASE classname |
| 类实现的全部接口 | CLASS_IMPLEMENT_INTERFACE_LIST classname |
| 类是否违背信息隐藏原则 | CLASS_INFO_HIDDEN classname |
第十四次作业：
在上次作业基础上，扩展解析器，使得能够支持对 UML 顺序图和 UML 状态图的解析，并能够支持几个基本规则的验证。
实现指令：
| 给定状态机模型中一共有多少个状态 | STATE_COUNT statemachine_name |
|---|---|
| 给定状态机模型中一共有多少个迁移 | TRANSITION_COUNT statemachine_name |
| 给定状态机模型和其中的一个状态，有多少个不同的后继状态 | SUBSEQUENT_STATE_COUNT statemachine_name statename |
| 给定UML顺序图，一共有多少个参与对象 | PTCP_OBJ_COUNT umlinteraction_name |
| 给定UML顺序图，一共有多少个交互消息 | MESSAGE_COUNT umlinteraction_name |
| 给定UML顺序图和参与对象，有多少个incoming消息 | INCOMING_MSG_COUNT umlinteraction_name lifeline_name |
| R001：针对下面给定的模型元素容器，不能含有重名的成员(UML002) | |
| R002：不能有循环继承(UML008) | |
| R003：任何一个类或接口不能重复继承另外一个接口(UML009) |
关键点 1 —— UML 规则：
准确理解 UML 规则，然后使用 Java 来实现相应的接口。
关键点 2 —— 架构设计：
第一次作业和第二次作业紧密相关，要考虑好可扩展性。
二、UML 设计
三、两次次作业的类图与度量分析
度量分析标识：
- ev(G) 本质复杂度
- iv(G) 设计复杂度
- v(G) 循环复杂度
- OCavg 平均方法复杂度
- OSavg 平均方法语句数（规模）
- WMC 加权方法复杂度
- v(G)avg 平均循环复杂度
- v(G)tot 总循环复杂度
第十三次作业：
1、架构构思：
第一次作业主要是继承 UmlInteraction 接口，实现相应的方法。
我的设计是首先在 MyUmlInteraction 进行构造，读取所有的元素，然后在 Find 里用 HashMap 进行存储， MyAssociation 、 MyInterfaceRealition 和 MyGeneralization 等直接查找好相应的类和接口，直接保存，方便查找。
同时在 Cahce 里设置缓存，记录重复信息和每次查询后结果的存储，保证不做重复查找，提高效率。
然后 MyUmlInteraction 中的每条指令都归类到相应的结构中，互不影响，例如：
| getClassOperationCount | Find.getClassByName(className).getOperationCount(queryType)** |
|---|---|
| getClassAttributeCount | Find.getClassByName(className).getAttributeSize() |
| getClassOperationVisibility | Find.getClassByName(className).getOperationVisibility( operationName) |
| getTopParentClass | Find.getClassByName(className).getTopFatherName() |
其中 Find.getClassByName(className) 得到是 MyClass ，在这个类中包含相应的属性：
private UmlClass umlClass;
private HashMap<String, UmlAttribute> attributeNameMap;
private HashMap<String, MyOperation> operationIdMap;
private HashMap<OperationQueryType, Integer> operaCountMap;
private HashMap<String, HashMap<Visibility, Integer>> operaVisiMap;
private LinkedList<MyClass> fatherList;
private LinkedList<AttributeClassInformation> attributeInformationList;
private HashSet<String> interfaceIdSet;
private int assoicationCount;
private HashSet<String> assoicationIdSet; 类似的， MyInterface 和 MyOperation 也是一样。
2、项目分析：
类图分析：
度量分析：
3、自我总结：
这次作业的复杂度问题主要就是 MyPath.compareTo() 和 Mypath.equals()，这两个方法的 ev(G) 都在 Metrics 中出现了飘红。
然而这个问题也是没有办法的，equals() 中我们可以先检查 hash 是否相等，如果相等再进行循环检查。
而 compareTo() 则只能一股脑的检查下去，判断大小。
所以循环是没有办法避免的。
而 MyPathContainer.addPath() 的 v(G) 虽然没有飘红，但是复杂度最高的原因在于，我将 getDistinctNodeCount() 分摊到了每一次 add 和 remove ：
1 for (Integer pathId : path) {
2 if (distinctNode.containsKey(pathId)) {
3 distinctNode.put(pathId, distinctNode.get(pathId) + 1);
4 } else {
5 distinctNode.put(pathId, 1);
6 }
7 } 其他方法的复杂度都得到了有效的控制。
4、程序bug分析：
这次作业比较简单，我的中测提交主要是不断简化程序，降低算法复杂度。我是严格按照 JML 规格编写的，所以并没有出现 bug。
5、性能分析：
一方面我将 getDistinctNodeCount() 这一耗时利器分摊到了每一次 add 和 remove ，减少时间消耗。
另一方面我从讨论区中张万聪大佬的帖子中受教，根据id和路径双向索引，使用 HashMap 双容器，一个是 HashMap<Integer, Path> ，一个是 HashMap<Path, Integer>，增删时同时考虑双方，查找就可以根据不同索引进行选择，保证了性能。
第十四次作业：
1、架构构思：
本次作业的架构概况起来就是“大胆继承，小心重构”。
因为 Graph 接口是继承了 PathContainer 接口的，所以我的 MyGraph 直接继承了上一次作业的 MyPathContainer 。
从指令上来看，上一次作业主要是涉及点结构，而第二次作业的重点在边结构。在上一次作业中，我将 getDistinctNodeCount() 这一耗时利器分摊到了每一次 add 和 remove ，那么针对这一次作业，我需要重写 addPath() 、removePath() 和 removePathById() ，继续将每一次的增加和删除操作分摊下去。
同时设置 isModify 变量作为图结构的更新的标志。
而针对新的指令扩展，因为“本次由路径构成的图结构，在任何时候，总节点个数（不同的节点个数，即 DISTINCT_NODE_COUNT 的结果），均不得超过250”，所以我采用静态数组，将节点离散化，把它们映射到[1,250]。
针对最短路径，使用 Bfs 算法，采用 cache 机制，将每次计算目标结点之间距离时经过的中间结点的距离都保存下来，如果 isModify 被置 true，则清空 cache，重新计算。
2、项目分析：
类图分析：
度量分析：
3、自我总结：
这次作业中的飘红主要是 graph.MyPath.compareTo()、graph.MyPath.equals()、graph.MyGraph.bfs() 和 graph.MyGraph.cache()，其中 graph.MyPath.compareTo() 和 graph.MyPath.equals() 在上次作业中已经分析过了，并没有办法降低 ev(G)。
bfs() 属于标准算法，而 cache() 中牵扯到一个图的重构，这两个方法我在第十一次作业中进行了再一次重构，将复杂度降低了下去。在本次作业中的 cache() ，我是这样写的：
1 for (int i = 0; i < super.getLength(); i++) {
2 for (int j = 0; j < super.getLength(); j++) {
3 if (i == j) {
4 renewGraph[i][j] = 0;
5 } else if (graph[i][j] == 0) {
6 renewGraph[i][j] = inf;
7 } else {
8 renewGraph[i][j] = 1;
9 }
10 }
11 } 然而实际上只需要修改一下 bfs() ，在需要的时候判断一下，就能省去这个 O(n2) 的方法。当时可能是脑子轴了，没有想到。
4、程序bug分析：
这次作业我的强测爆的极其惨烈，原因在意“小心重构”的“小心”二字我没有做到。
bug 出现在 MyPathContainer.removePath() 和 MyPathContainer.removePathById()。
为了将图的更新均摊到每一次 remove 操作，最初我是这样写的：
1 if (distinctNode.get(pathId) == 1) {
2 distinctNode.remove(pathId);
3 removeList.add(removeId);
4 mapping.remove(pathId);
5
6 for (int i = 0; i < length; i++) {
7 if (graph[removeId][i] != 0) {
8 graph[removeId][i] = 0;
9 graph[i][removeId] = 0;
10 }
11 }
12 } else {
13 distinctNode.put(pathId, distinctNode.get(pathId) - 1);
14 if (graph[removeId][prevId] != 0 && removeId != prevId) {
15 graph[removeId][prevId] = 0;
16 graph[prevId][removeId] = 0;
17 }
18 }每一次删除操作，我都将这个 Path 中的节点的所有边全部删除，如此错误的写法我当时居然没发现，实属不应该。
因为这个头昏的写法，我的强测炸的妈都找不着了。
5、性能分析：
性能方面，MyGraph 继承了上一次作业的 MyPathContainer ，相关方法的复杂度得到有效控制。
而本次作业相关的图操作，除了我上文提到的 cache() 的简化问题，bfs 最多跑 20×n 次，每次复杂度O(V + E)，所以复杂度完全可以接受。