迭代器模式介绍
迭代器模式就像日常使用的Iterator方法遍历。虽然这种设计模式在实际业务开发中用得并不多，但却要使用JDK提供的list集合遍历。另外，增强的for循环语句虽然是循环输出数据，但并不是迭代器模式。迭代器模式的特点是实现Iterable接口，通过next方式获取集合元素，同时具备删除元素等操作功能；而增强的for循环语句是无法实现的。
迭代器模式的优点是能够以相同的方式遍历不同的数据结构元素，这些数据结构包括数组、链表和树等。而用户在使用遍历时，并不需要关心每一种数据结构的遍历处理逻辑，做到让使用变得统一易用。
组织架构树形结构遍历场景
模拟迭代遍历，并输出公司中具有树形结构的组织架构关系中的雇员列表。
红线：深度遍历 1、2、4、5、6、7、8、3
大部分公司的组织架构呈金字塔结构，也就是树形结构，分为一级、二级和三级等部门，每个组织部门由雇员填充，最终呈现出一个整体的树形组织架构。一般常用的遍历采用JDK默认提供的方法，对list集合遍历。但是对于业务特性较大的树形结构，如果需要使用遍历方法，可以自己实现。接下来会把以上组织层次关系用树形结构实现，并完成迭代功能。
迭代器模式遍历组织结构
迭代器模式主要分为一下几个模块：
- Collection：集合方法部分用于对自定义的数据结构添加通用方法，包括add、remove、iterator等核心方法。
- Iterable：提供获取迭代器，这个接口类会被Collection继承
- Iterator：提供了两个方法的定义，包括hasNext、next，会在具体的数据结构中编写实现方式。
除了以上通用的迭代器实现方式，组织关系结构树是由节点间的关系链构成的，所以会比上述的内容多一些入参。
左侧是迭代器定义，右侧是在数据结构中实现迭代器功能。左侧部分的实现与JDK中的实现方式一样，所以在学习过程中可以互相参考，也可以扩展学习。为了便于理解，这里实现了一种比较简单的树形结构深度遍历方式。读者也可以把遍历扩展为横向遍历，也是宽度遍历。
雇员实体类
1
2
3
4
5
6
7
8
| @Data
@AllArgsConstructor
@NoArgsConstructor
public class Employee {
private String uId;
private String name;
private String desc;
}
|
树节点链路
1
2
3
4
5
6
7
| @Data
@NoArgsConstructor
@AllArgsConstructor
public class Link {
private String formId;
private String toId;
}
|
迭代器定义
1
2
3
4
| public interface Iterator<E>{
boolean hasNext();
E next();
}
|
这个类和Java的JDK中提供的类是一样的，读者可以对照Java中list集合的iterator方法学习。hasNext()用于判断是否有下一个元素，next()用于获取下一个元素，这个在Java中list集合的遍历中经常会用到。
可迭代接口定义
1
2
3
| public interface Iterable <E>{
Iterator<E> iterator();
}
|
这个接口提供了迭代器的实现Iterator的获取方式，也就是在自己的数据结构中实现迭代器功能，并交给Iterable，由此让外部调用方式获取并使用。
集合功能接口定义
1
2
3
4
5
6
7
| public interface Collection<E,L> extends Iterable<E>{
boolean add(E e);
boolean remove(E e);
boolean addLink(String key, L l);
boolean removeLink(String key);
Iterator<E> iterator();
}
|
这里定义集合造作接口Collection，同时继承另外一个接口Iterable的方法iterator()。以后无论谁可以实现这个接口，都需要实现上述定义的一些基本功能:添加元素、删除元素和遍历。有读者可能注意到这里定义了两个泛型<E,L>,因为在数据结构中，一个用于添加元素，另一个用于添加树节点的链路关系。
迭代器功能实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| public class GroupStructure implements Collection<Employee,Link> {
private String groupId;
private String groupName;
private Map<String,Employee> employeeMap = new ConcurrentHashMap<>();
private Map<String, List<Link>> linkMap = new ConcurrentHashMap<>();
private Map<String, String> invertedMap = new ConcurrentHashMap<>();
public GroupStructure(String groupId,String groupName){
this.groupId = groupId;
this.groupName = groupName;
}
@Override
public boolean add(Employee employee) {
return null != employeeMap.put(employee.getUId(),employee);
}
@Override
public boolean remove(Employee employee) {
return null != employeeMap.remove(employee.getUId());
}
@Override
public boolean addLink(String key, Link link) {
invertedMap.put(link.getToId(),link.getFormId());
if (linkMap.containsKey(key)){
return linkMap.get(key).add(link);
}else {
List<Link> links = new ArrayList<Link>();
links.add(link);
linkMap.put(key,links);
return true;
}
}
@Override
public boolean removeLink(String key) {
return null != linkMap.remove(key);
}
@Override
public Iterator<Employee> iterator() {
return new Iterator<Employee>() {
HashMap<String,Integer> keyMap = new HashMap<String,Integer>(16);
int totalIdx = 0;
private String fromId = groupId;
private String toId = groupId;
@Override
public boolean hasNext() {
return totalIdx < employeeMap.size();
}
@Override
public Employee next() {
List<Link> links = linkMap.get(toId);
int cursorIdx = getCursorIdx(toId);
if (links == null){
cursorIdx = getCursorIdx(fromId);
links = linkMap.get(fromId);
}
while (cursorIdx > links.size() - 1){
fromId = invertedMap.get(fromId);
cursorIdx = getCursorIdx(fromId);
links = linkMap.get(fromId);
}
Link link = links.get(cursorIdx);
toId = link.getToId();
fromId = link.getFormId();
totalIdx++;
return employeeMap.get(link.getToId());
}
public int getCursorIdx(String key){
int idx = 0;
if (keyMap.containsKey(key)){
idx = keyMap.get(key);
keyMap.put(key,++idx);
}else {
keyMap.put(key,idx);
}
return idx;
}
};
}
}
|
这部分代码主要包括了添加元素和删除元素。最重要的是对遍历实现new Iterator。添加和删除元素相对来说比较简单，使用了两个Map数组结构定义雇员列表、组织架构关系id->list。当添加元素时，会分别在不同的方法中向Map结构填充指向关系，也就构建出了树形组织关系。
- 对于树形结构，需要做的是深度遍历，也就是对左侧一直遍历，直至遍历到最深的节点。
- 当遍历到最深的节点后，开始遍历它的横向节点。
- 当遍历完成横向节点后，则向顶部寻找还未遍历的横向节点，直至树形结构全部遍历完成。
测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public class Test {
public static void main(String[] args) {
GroupStructure groupStructure = new GroupStructure("1","rookie");
groupStructure.add(new Employee("2","花花","二级部门"));
groupStructure.add(new Employee("3","豆包","二级部门"));
groupStructure.add(new Employee("4","蹦蹦","三级部门"));
groupStructure.add(new Employee("5","大烧","三级部门"));
groupStructure.add(new Employee("6","虎哥","四级部门"));
groupStructure.add(new Employee("7","玲姐","四级部门"));
groupStructure.add(new Employee("8","秋雅","四级部门"));
groupStructure.addLink("1",new Link("1","2"));
groupStructure.addLink("1",new Link("1","3"));
groupStructure.addLink("2",new Link("2","4"));
groupStructure.addLink("2",new Link("2","5"));
groupStructure.addLink("5",new Link("5","6"));
groupStructure.addLink("5",new Link("5","7"));
groupStructure.addLink("5",new Link("5","8"));
Iterator<Employee> iterator = groupStructure.iterator();
while (iterator.hasNext()){
Employee employee = iterator.next();
System.out.println(employee.toString());
}
}
}
|
总结
从以上的功能可以看到，迭代器的设计模式满足了单一职责原则和开闭原则，外接的调用方不需要知道任何一个不同的数据结构在使用上的遍历差异，非常方便扩展，也让整个遍历变得更加干净、整洁。但从结构的实现上可以看到，迭代器模式的实现过程相对比较复杂。在类的实现上扩展需要外部定义的类，使得遍历与原始数据结构分开了。虽然比较麻烦，但可以看在使用JDK时，迭代器的模式还是很好用的，扩展和升级非常方便。
