53 | 组合模式：如何设计实现支持递归遍历的文件系统目录树结构？

组合模式： 当数据结构呈现树状，可以使用递归处理每一处节点的数据。 感觉名字有点迷惑，应该叫做树状模式

把子数抽象成一类对象，并且增加数量等属性，这样就避免了多次的迭代。

课堂讨论： 实质是"递归代码要警惕重复计算"问题！可以用散列表存储每个(path,size)，通过路径直接返回对应的size,删除或者添加的时候，维护这个size即可。 参看争哥《数据结构与算法之美》第十讲：为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。

课堂讨论 可以把计算文件数量和大小的逻辑抽出来，定义两个成员变量文件大小和文件数量； 在每次addSubNode()和removeSubNode()的时候去调用计算逻辑，更新文件大小和文件数量； 这样在调用countNumOfFiles和countSizeOfFiles的时候直接返回我们的成员变量就好了； 当然如果这么做的话，那countNumOfFiles和countSizeOfFiles这两个方法的名字也不合适了，应该叫numOfFiles和sizeOfFiles

tomcat的多层容器也是使用了组合模式。只需要调用最外层容器Server的init方法，整个程序就起来了。客户端只需要处理最外层的容器，就把整个系统拎起来了。 组合模式使用了树形的数据结构以及递归算法，这里也可以看出知识的相通性（算法和设计模式）。想到这方面的另外一个例子就是责任链模式，责任链模式就是使用了数据结构中的链表和递归算法。

把计算逻辑放在addSubNode和removeSubNode里面

我想的一个思路是：每个节点新增一个field：parent，父链接指向它的上层节点，同时增加字段numOfFiles，sizeOfFiles。对于File节点：numOfFiles=1， sizeOfFiles=它自己的大小。对于Directory节点，是其子节点的和。删除、增加subnode时，只需要从下向上遍历一个节点的parent link，修改numOfFiles和sizeOfFiles。这样的话删除、新增subnode修改值的复杂度为树的深度，查询返回numOfFiles和sizeOfFiles复杂度为O(1)。

真的是没有最适合，只有更适合 实际工作中碰到过一个场景需要抽象出条件和表达式来解决的。一个表达式可以拥有N个子表达式以及条件，这个表达式还有一个属性and、or来决定所有子表达式/条件是全部成立还是只要有一个成立，这个表达式就成立。 当时做的时候真是各种绕，这种场景真的非常适合组合模式，能大大简化代码的实现难度，提高可读、可维护性

设计模式_53: # 作业 可以做文件数和文件大小的缓存，更新缓存时要考虑实时性与性能的平衡。 # 感想 今天的内容，联想到Linux“一切皆文件”的设计思想。 好像天然就觉得应该这样做，但是，还能怎么做呢？ 还能。。。把Directory和File设计成不想关的两个类，这样又有什么问题呢？ 不过是Directory维护两个List(file/directory),维护两套方法，add/removeFile,add/removeDirectory。。。这当然没有以前简洁，但也没有特别复杂吧。。。 后面又想到，如果File还分很多类型: TxtFile/ImageFile/ExeFile/...,Directory(这里是广义的集合)也可以有多种: LinearDirectory/GridDirectory/CircleDirectory/... 这样会不会导致处理逻辑的爆炸，你会说：当然不会啊，所有的类型最终会抽象为File和Directory两种类型啊！ 既然都抽象了，何不彻底一点，把File和Directory也抽象为一种类型: Everything is a File.

//每一级目录保存本级目录中的文件数和文件Size，Count时递归统计所有子目录 public class Directory extends FileSystemNode { private List<FileSystemNode> subNodes = new ArrayList<>(); private Map<String,FileSystemNode> subDirectory = new HashMap<>(); private int _numOfFiles = 0; private long _sizeofFiles = 0; public Directory(String path) { super(path); } @Override public int countNumOfFiles() { int numOfFiles = 0; for (FileSystemNode fileOrDir : subDirectory.values()) { numOfFiles += fileOrDir.countNumOfFiles(); } return numOfFiles + _numOfFiles; } @Override public long countSizeOfFiles() { long sizeofFiles = 0; for (FileSystemNode fileOrDir : subDirectory.values()) { sizeofFiles += fileOrDir.countSizeOfFiles(); } return sizeofFiles + _sizeofFiles; } public void addSubNode(FileSystemNode fileOrDir) { if(fileOrDir instanceof Directory) { subDirectory.put(fileOrDir.getPath(),fileOrDir); } else { _numOfFiles++; _sizeofFiles += fileOrDir.countSizeOfFiles(); subNodes.add(fileOrDir); } } public void removeSubNode(FileSystemNode fileOrDir) { if(fileOrDir instanceof Directory) { subDirectory.remove(fileOrDir.getPath()); return; } int size = subNodes.size(); int i = 0; for (; i < size; ++i) { if (subNodes.get(i).getPath().equalsIgnoreCase(fileOrDir.getPath())) { break; } } if (i < size) { subNodes.remove(i); _numOfFiles--; _sizeofFiles -= fileOrDir.countSizeOfFiles(); } } }