迭代器模式

╰半夏微凉° 2022-10-16 15:21 26阅读 0赞

## 一、前言 ##

`相信相信的力量！`

从懵懂的少年，到拿起键盘，可以写一个HelloWorld。多数人在这并不会感觉有多难，也不会认为做不出来。因为这样的例子，有老师的指导、有书本的例子、有前人的经验。但随着你的开发时间越来越长，要解决更复杂的问题或者技术创新，因此在网上搜了几天几夜都没有答案，这个时候是否想过放弃，还是一直坚持不断的尝试一点点完成自己心里要的结果。往往这种没有前车之鉴需要自己解决问题的时候，可能真的会折磨到要崩溃，但你要愿意执着、愿意倔强，愿意选择相信相信的力量，就一定能解决。哪怕解决不了，也可以在这条路上摸索出其他更多的收获，为后续前进的道路填充好垫脚石。

`时间紧是写垃圾代码的理由？`

拧螺丝？Ctrl+C、Ctrl+V？贴膏药一样写代码？没有办法，没有时间，往往真的是借口，胸中没用笔墨，才只能凑合。难道一定是好好写代码就浪费时间，拼凑CRUD就快吗，根本不可能的。因为不会，没用实操过，很少架构出全场景的设计，才很难写出优良的代码。多增强自身的编码(`武术`)修为，在各种编码场景中让自己变得老练，才好应对紧急情况下的需求开发和人员安排。就像韩信一样有谋有略，才能执掌百万雄兵。

`不要只是做个工具人！`

因为日常的编写简单业务需求，导致自己像个工具人一样，日久天长的也就很少去深入学习更多技术栈。看见有工具、有组件、有框架，拿来就用用，反正没什么体量也不会出什么问题。但如果你想要更多的收入，哪怕是重复的造轮子，你也要去尝试造一个，就算不用到生产，自己玩玩总可以吧。有些事情只有自己经历过，才能有最深的感触，参与过实践过，才好总结点评学习。

## 二、开发环境 ##

1.  JDK 1.8
2.  Idea + Maven
3.  涉及工程一个，可以通过关注**公众号**：[`bugstack虫洞栈`][bugstack]，回复`源码下载`获取(打开获取的链接，找到序号18)

<table> 
 <thead> 
  <tr> 
   <th>工程</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>itstack-demo-design-15-00</td> 
   <td>开发树形组织架构关系迭代器</td> 
  </tr> 
 </tbody> 
</table>

## 三、迭代器模式介绍 ##

![迭代器模式，图片来自 refactoringguru.cn][refactoringguru.cn]

迭代器模式，常见的就是我们日常使用的`iterator`遍历。虽然这个设计模式在我们的实际业务开发中的场景并不多，但却几乎每天都要使用`jdk`为我们提供的`list`集合遍历。另外增强的for循环虽然是循环输出数据，但是他不是迭代器模式。迭代器模式的特点是实现`Iterable`接口，通过`next`的方式获取集合元素，同时具备对元素的删除等操作。而增强的for循环是不可以的。

这种设计模式的优点是可以让我们以相同的方式，遍历不同的数据结构元素，这些数据结构包括；`数组`、`链表`、`树`等，而用户在使用遍历的时候并不需要去关心每一种数据结构的遍历处理逻辑，从让使用变得统一易用。

## 四、案例场景模拟 ##

![场景模拟；公司树形组织架构][e7f7a8c6b2b7fa51a77ba28142878860.png]

**在本案例中我们模拟迭代遍历输出公司中树形结构的组织架构关系中雇员列表**

大部分公司的组织架构都是金字塔结构，也就这种树形结构，分为一级、二级、三级等部门，每个组织部门由雇员填充，最终体现出一个整体的树形组织架构关系。

一般我们常用的遍历就是jdk默认提供的方法，对list集合遍历。但是对于这样的偏业务特性较大的树形结构，如果需要使用到遍历，那么就可以自己来实现。接下来我们会把这个组织层次关系通过树形数据结构来实现，并完成迭代器功能。

## 五、迭代器模式遍历组织结构 ##

在实现迭代器模式之前可以先阅读下`java`中`list`方法关于`iterator`的实现部分，几乎所有的迭代器开发都会按照这个模式来实现，这个模式主要分为以下几块；

1.  Collection，集合方法部分用于对自定义的数据结构添加通用方法；`add`、`remove`、`iterator`等核心方法。
2.  Iterable，提供获取迭代器，这个接口类会被`Collection`继承。
3.  Iterator，提供了两个方法的定义；`hasNext`、`next`，会在具体的数据结构中写实现方式。

除了这样通用的迭代器实现方式外，我们的组织关系结构树，是由节点和节点间的关系链构成，所以会比上述的内容多一些入参。

### 1. 工程结构 ###

itstack-demo-design-15-00
    └── src
        ├── main
        │   └── java
        │       └── org.itstack.demo.design
        │           ├── group
        │           │	├── Employee.java
        │           │	├── GroupStructure.java
        │           │	└── Link.java
        │           └──  lang
        │            	├── Collection.java
        │            	├── Iterable.java
        │            	└── Iterator.java
        └── test
            └── java
                └── org.itstack.demo.design.test
                    └── ApiTest.java

**迭代器模式模型结构**

![迭代器模式模型结构][58fcf61b32a41e0d7c086c0b3a9e741f.png]

*  以上是我们工程类图的模型结构，左侧是对迭代器的定义，右侧是在数据结构中实现迭代器功能。
 *  关于左侧部分的实现与jdk中的方式是一样的，所以在学习的过程中可以互相参考，也可以自己扩展学习。
 *  另外这个遍历方式一个树形结构的深度遍历，为了可以更加让学习的小伙伴容易理解，这里我实现了一种比较简单的树形结构深度遍历方式。*后续读者也可以把遍历扩展为横向遍历也就是宽度遍历。*

### 2. 代码实现 ###

2.1 雇员实体类

/**
     * 雇员
     */
    public class Employee {
    
        private String uId;   // ID
        private String name;  // 姓名
        private String desc;  // 备注
        
        // ...get/set
    }

*  这是一个简单的雇员类，也就是公司员工的信息类，包括必要的信息；id、姓名、备注。

2.2 树节点链路

/**
     * 树节点链路
     */
    public class Link {
    
        private String fromId; // 雇员ID
        private String toId;   // 雇员ID    
        
        // ...get/set
    }

*  这个类用于描述结构树中的各个节点之间的关系链，也就是`A to B`、`B to C`、`B to D`，以此描述出一套完整的树组织结构。

2.3 迭代器定义

public interface Iterator<E> {
    
        boolean hasNext();
    
        E next();
        
    }

*  这里的这个类和`java`的`jdk`中提供的是一样的，这样也方面后续读者可以对照`list`的`Iterator`进行源码学习。
 *  方法描述；`hasNext`，判断是否有下一个元素、`next`，获取下一个元素。这个在`list`的遍历中是经常用到的。

2.4 可迭代接口定义

public interface Iterable<E> {
    
        Iterator<E> iterator();
    
    }

*  这个接口中提供了上面迭代器的实现`Iterator`的获取，也就是后续在自己的数据结构中需要实现迭代器的功能并交给`Iterable`，由此让外部调用方进行获取使用。

2.5 集合功能接口定义

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>`，因为我们的数据结构一个是用于添加元素，另外一个是用于添加树节点的链路关系。

2.6 (核心)迭代器功能实现

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.  当横向节点遍历完成后则向上寻找横向节点，直至树结构全部遍历完成。

### 3. 测试验证 ###

3.1 编写测试类

@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", "秋雅", "四级部门"));   
        
        // 节点关系 1->(1,2) 2->(4,5)
        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());
        }
    }

3.2 测试结果

22:23:37.166 [main] INFO  org.itstack.demo.design.test.ApiTest - 二级部门，雇员 Id：2 Name：花花
    22:23:37.168 [main] INFO  org.itstack.demo.design.test.ApiTest - 三级部门，雇员 Id：4 Name：蹦蹦
    22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - 三级部门，雇员 Id：5 Name：大烧
    22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - 四级部门，雇员 Id：6 Name：虎哥
    22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - 四级部门，雇员 Id：7 Name：玲姐
    22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - 四级部门，雇员 Id：8 Name：秋雅
    22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - 二级部门，雇员 Id：3 Name：豆包
    
    Process finished with exit code 0

*  从遍历的结果可以看到，我们是顺着树形结构的深度开始遍历，一直到右侧的节点**3**；`雇员 Id：2、雇员 Id：4...雇员 Id：3`

## 六、总结 ##

*  迭代器的设计模式从以上的功能实现可以看到，满足了单一职责和开闭原则，外界的调用方也不需要知道任何一个不同的数据结构在使用上的遍历差异。可以非常方便的扩展，也让整个遍历变得更加干净整洁。
 *  但从结构的实现上可以看到，迭代器模式的实现过程相对来说是比较负责的，类的实现上也扩增了需要外部定义的类，使得遍历与原数据结构分开。虽然这是比较麻烦的，但可以看到在使用java的jdk时候，迭代器的模式还是很好用的，可以非常方便扩展和升级。
 *  以上的设计模式场景实现过程可能对新人有一些不好理解点，包括；迭代器三个和接口的定义、树形结构的数据关系、树结构深度遍历思路。这些都需要反复实现练习才能深入的理解，事必躬亲，亲历亲为，才能让自己掌握这些知识。

[bugstack]: https://bugstack.cn/assets/images/qrcode.png
[refactoringguru.cn]: /images/20221014/12c54a5dc772448dbb8bf63eb68f8b32.png
[e7f7a8c6b2b7fa51a77ba28142878860.png]: /images/20221014/d69636e63fe74ff983963143d0d442fb.png
[58fcf61b32a41e0d7c086c0b3a9e741f.png]: /images/20221014/471dbadad17e4db0a3bb1a0b28dd245c.png