# 设计模式之迭代器模式
> 来源自《重学Java设计模式》[链接](https://pan.baidu.com/s/1dUMCff7S5Qb-vsJFw28AZg
)提取码：ytc3
## 迭代器模式
迭代器模式，常见的就是我们日常使用的`iterator`遍历。虽然这个设计模式在我们的实际业务开发中的场景并不多，但却几乎每天都要使用`jdk`为我们提供的`list`集合遍历。另外增强for循环虽然时循环输出数据，但是它不是迭代器模式。迭代器模式的特点时实现`iterator`接口，通过`next`的方式获取集合元素，同时具备对元素的删除等操作。而增强for循环是不可以的。
这种设计模式的优点的可以让我们以相同的方式，遍历不同的数据结构元素，这些数据结构包括：`数组`，`链表`，`树`等，而用户在使用遍历的时候并不需要去关心每一种数据结构的遍历处理逻辑，从而让使用变得统一易用。
## 案例场景模拟
在本案例中我们模拟迭代遍历出公司中树形结构的组织架构关系中雇员列表
大部分公司的组织架构都是金字塔结构，也就是这种树形结构，分为一级、二级、三级等部门，每个组织部门由雇员填充，最终体现出一个整体的树形组织架构关系。
一般我们常用的遍历就是jdk默认提供的方法，对list集合遍历。但是对于这样的偏业务特性较大的树形结构，如果需要使用到遍历，那么就可以自己来实现。接下来我们会把这个组织层次关系通过树形数据结构来实现，并完成迭代器功能。
## 迭代器模式遍历组织结构
在实现迭代器模式之前可以先阅读下`java`中`list`方法关于`iterator`的实现部分，几乎所有的迭代器开发都会按照这个模式来实现，这个模式主要分为以下几块：
1. Collection，集合方法部分用于自定义的数据结构添加通用方法：`add`、`remove`、`iterator`等核心方法。
2. Iterable，提供获取迭代器，这个接口类是被`Collection`继承。
3. Iterator，提供了两个方法的定义：`hasNext`、`next`，会由节点和节点间的关系链构成，所以会比上述的内容多一些入参。
**迭代器模式模型结构**
- 以上是我们工程类图的模型结构，左侧是对迭代器的定义，右侧是在数据结构中实现迭代器功能。
- 关于左侧部分的实现与jdk中的方式是一样的，所以在学习的过程中可以互相参考，也可以自己扩展学习。
### 代码实现
#### 雇员实体类
```java
public class Employee {
private String uId; // ID
private String name; // 姓名
private String desc; // 备注
private ArrayList<String> num;
public Employee(String uId, String name) {
this.uId = uId;
this.name = name;
}
public Employee(String uId, String name, String desc) {
this.uId = uId;
this.name = name;
this.desc = desc;
}
public String getuId() {
return uId;
}
public void setuId(String uId) {
this.uId = uId;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getDesc() {
return desc;
}
public void setDesc(String desc) {
this.desc = desc;
}
}
```
- 这是一个简单的雇员类，也就是公司员工的信息类，包括必要的信息：id、姓名、备注。
#### 树节点链路
```java
public class Link {
private String fromId; // 雇员ID
private String toId; // 雇员ID
public Link(String fromId, String toId) {
this.fromId = fromId;
this.toId = toId;
}
public String getFromId() {
return fromId;
}
public void setFromId(String fromId) {
this.fromId = fromId;
}
public String getToId() {
return toId;
}
public void setToId(String toId) {
this.toId = toId;
}
}
```
- 这个类用于描述结构树中的各个节点之间的关系链，也就是`A to B`、`B to C`、`B to D`，以此描述出一套完整的树组织结构。
#### 迭代器定义
```java
public interface Iterator<E> {
boolean hasNext();
E next();
}
```
#### 可迭代接口定义
```java
public interface Iterable<E> {
Iterator<E> iterator();
}
```
- 这个接口中提供了上面迭代器的实现`Iterator`的获取，也就是后续在自己的数据结构中需要实现迭代器的功能并交给`Iterable`，由此让外部调用方进行使用。
#### 集合功能接口定义
```java
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`，同时继承另外一个接口`Iterator`的方法`iterator()`。这样后续谁来实现这个接口，就需要实现上述定义的一些基本功能：`添加元素`、`删除元素`、`遍历`.
- 同时你可能注意到这里定义了两个泛型`<E,L>`，因为我们的数据结构是一个用于添加元素，另外一个用于添加树节点的链路关系。
#### （核心）迭代器功能实现
```java
public class GroupStructure implements Collection<Employee, Link> {
private String groupId; // 组织ID，也是一个组织链的头部ID
private String groupName; // 组织名称
private Map<String, Employee> employeeMap = new ConcurrentHashMap<String, Employee>(); // 雇员列表
private Map<String, List<Link>> linkMap = new ConcurrentHashMap<String, List<Link>>(); // 组织架构关系；id->list
private Map<String, String> invertedMap = new ConcurrentHashMap<String, String>(); // 反向关系链
public GroupStructure(String groupId, String groupName) {
this.groupId = groupId;
this.groupName = groupName;
}
public boolean add(Employee employee) {
return null != employeeMap.put(employee.getuId(), employee);
}
public boolean remove(Employee o) {
return null != employeeMap.remove(o.getuId());
}
public boolean addLink(String key, Link link) {
invertedMap.put(link.getToId(), link.getFromId());
if (linkMap.containsKey(key)) {
return linkMap.get(key).add(link);
} else {
List<Link> links = new LinkedList<Link>();
links.add(link);
linkMap.put(key, links);
return true;
}
}
public boolean removeLink(String key) {
return null != linkMap.remove(key);
}
public Iterator<Employee> iterator() {
return new Iterator<Employee>() {
HashMap<String, Integer> keyMap = new HashMap<String, Integer>();
int totalIdx = 0;
private String fromId = groupId; // 雇员ID，From
private String toId = groupId; // 雇员ID，To
public boolean hasNext() {
return totalIdx < employeeMap.size();
}
public Employee next() {
List<Link> links = linkMap.get(toId);
int cursorIdx = getCursorIdx(toId);
// 同级节点扫描
if (null == links) {
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.getFromId();
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<Employee>`。
- 添加和删除元素相对来说比较简单，使用了两个map数组结构进行定义：`雇员列表`，`组织架构关系：id->list`。当元素添加元素的时候，会分别在不同的方法中向`map`中进行填充**指向关系（A->B）**，也就构建出了我的树形组织结构关系。
**迭代器实现思路**
1. 这里的树形结构我们需要做的是深度遍历，也就是左侧的一直遍历到最深节点。
2. 当遍历到最深节点后，开始遍历最深节点的横向节点。
3. 当横向节点遍历完成后则向上寻找横向节点，直至树结构全部遍历完成。
#### 测试验证
##### 测试类
```java
public class ApiTest {
private Logger logger = LoggerFactory.getLogger(ApiTest.class);
@Test
public void test_iterator() {
GroupStructure groupStructure = new GroupStructure("1", "小傅哥");
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();
logger.info("{}，雇员 Id：{} Name：{}", employee.getDesc(), employee.getuId(), employee.getName());
}
}
}
```
**result**
```java
9:45:21.060 [main] INFO org.itstack.demo.design.test.ApiTest - 二级部门，雇员 Id：2 Name：花花
19:45:21.079 [main] INFO org.itstack.demo.design.test.ApiTest - 三级部门，雇员 Id：4 Name：蹦蹦
19:45:21.079 [main] INFO org.itstack.demo.design.test.ApiTest - 三级部门，雇员 Id：5 Name：大烧
19:45:21.079 [main] INFO org.itstack.demo.design.test.ApiTest - 四级部门，雇员 Id：6 Name：虎哥
19:45:21.079 [main] INFO org.itstack.demo.design.test.ApiTest - 四级部门，雇员 Id：7 Name：玲姐
19:45:21.079 [main] INFO org.itstack.demo.design.test.ApiTest - 四级部门，雇员 Id：8 Name：秋雅
19:45:21.080 [main] INFO org.itstack.demo.design.test.ApiTest - 二级部门，雇员 Id：3 Name：豆包
```
## 总结
- 迭代器的设计模式从以上的功能实现可以看到，满足了单⼀职责和开闭原则，外界的调用方也不需要知道任何⼀个不同的数据结构在使用上的遍历差异。可以非常方便的扩展，也让整个遍历变得更加干净整洁。
- 但从结构的实现上可以看到，迭代器模式的实现过程相对来说是比较负责的，类的实现上也扩增了需要外部定义的类，使得遍历与原数据结构分开。虽然这是比较麻烦的，但可以看到在使用java的jdk时候，迭代器的模式还是很好用的，可以非常方便扩展和升级。
