1, Foreword

Believe in the power of!

From ignorant teenagers to picking up the keyboard, you can write a HelloWorld. Most people don't think it's difficult or impossible to do it here. Because such examples include teachers' guidance, books and predecessors' experience. However, as your development time is getting longer and longer, you need to solve more complex problems or technological innovation. Therefore, you have searched the Internet for several days and nights without answers. At this time, do you want to give up or keep trying to achieve the results you want. Often, when you need to solve problems by yourself without learning from the past, you may really be tortured to collapse, but you must be willing to be persistent, stubborn and willing to choose the power to believe, and you will be able to solve them. Even if it can't be solved, you can find out more harvest on this road and fill the stepping stone for the follow-up road.

Is time constraints the reason for writing junk code?

Screw? Ctrl+C,Ctrl+V？ Write code like plaster? No way, no time, often really an excuse, no pen and ink in the chest, can only make do with it. Must it be a waste of time to write code well and put together CRUD quickly? It's impossible. Because I can't, I haven't used practical operation, and rarely construct the design of the whole scene, it's difficult to write good code. Enhance your coding (martial arts) accomplishments and become sophisticated in various coding scenes, so as to meet the needs of emergency developers and personnel arrangement. Just like Han Xin, only with strategy and strategy can he be in charge of millions of soldiers.

Don't just be a tool man!

Because of the daily writing of simple business requirements, I am like a tool man. Over time, I rarely learn more technology stacks in depth. If you see tools, components and frames, you can use them. Anyway, there is no volume and there will be no problem. But if you want more income, even if you build wheels repeatedly, you should also try to build one. Even if you don't need to produce, you can play by yourself. Only when you have experienced some things, can you have the deepest feelings. Only after you have participated in practice, can you summarize and comment on learning.

2, Development environment

1. JDK 1.8
2. Idea + Maven
3. One project involves official account number: bugstack wormhole stack Reply to the source code download (open the obtained link and find serial number 18)

engineering	describe
itstack-demo-design-15-00	Develop tree organization structure relationship iterator

3, Introduction to iterator mode

Iterator mode, which is commonly used in our daily iterator traversal. Although there are not many scenarios of this design pattern in our actual business development, we use the list set provided by jdk to traverse almost every day. In addition, the for loop output mode is not enhanced. The iterator mode is characterized by implementing the iteratable interface, obtaining the set elements by next, and deleting the elements. The enhanced for loop is not allowed.

The advantage of this design pattern is that it allows us to traverse different data structure elements in the same way, including; Arrays, linked lists, trees, etc. when using traversal, users do not need to care about the traversal processing logic of each data structure, so as to make the use unified and easy to use.

4, Case scenario simulation

In this case, we simulate iterative traversal to output the list of employees in the organizational structure relationship of the tree structure in the company

The organizational structure of most companies is a pyramid structure, that is, this tree structure is divided into primary, secondary and tertiary departments. Each organizational department is filled by employees, which finally reflects the overall tree organizational structure relationship.

Generally, our common traversal is the method provided by jdk by default to traverse the list collection. However, for such a tree structure with large partial business characteristics, if traversal needs to be used, it can be implemented by itself. Next, we will implement this organization hierarchy through tree data structure and complete the iterator function.

5, Iterator pattern traversal organization

Before implementing the iterator mode, you can first read the implementation part of the list method in java about iterator. Almost all iterator development will be implemented according to this mode. This mode is mainly divided into the following parts;

1. Collection, the collection method part is used to add general methods to custom data structures; Add, remove, iterator and other core methods.
2. Iterable, which provides an access iterator. This interface class will be inherited by the Collection.
3. Iterator, which provides definitions of two methods; hasNext and next, and the implementation method will be written in the specific data structure.

In addition to such a general iterator implementation, our organizational relationship structure tree is composed of nodes and relationship chains between nodes, so there will be more input parameters than the above contents.

1. Engineering structure

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

Iterator pattern model structure

• The above is the model structure of our engineering class diagram. On the left is the definition of iterator, and on the right is the realization of iterator function in data structure.
• The implementation of the left part is the same as that in jdk, so you can refer to each other in the process of learning, or you can expand your learning.
• In addition, this traversal method is a deep traversal of tree structure. In order to make it easier for learning partners to understand, I have implemented a relatively simple deep traversal of tree structure. Subsequent readers can also extend traversal to horizontal traversal, that is, width traversal.

2. Code implementation

2.1 employee entity

/**
 * employee
 */
public class Employee {

    private String uId;   // ID
    private String name;  // full name
    private String desc;  // remarks
    
    // ...get/set
}

• This is a simple employee class, that is, the information class of the company's employees, including necessary information; id, name and remarks.

2.2 tree node link

/**
 * Tree node link
 */
public class Link {

    private String fromId; // Employee ID
    private String toId;   // Employee ID    
    
    // ...get/set
}

• This class is used to describe the relationship chain between each node in the structure tree, that is, A to B, B to C and B to D, so as to describe a complete set of tree organization structure.

2.3 iterator definition

public interface Iterator<E> {

    boolean hasNext();

    E next();
    
}

• This class here is the same as that provided in the jdk of java. In this way, subsequent readers can learn the source code by referring to the Iterator of list.
• Method description; hasNext, judge whether there is a next element and next, and get the next element. This is often used in the traversal of the list.

2.4 iterative interface definition

public interface Iterable<E> {

    Iterator<E> iterator();

}

• This interface provides the implementation of the above Iterator and the acquisition of Iterator, that is, the function of Iterator needs to be implemented in its own data structure and handed over to Iterable, so that external callers can obtain and use it.

2.5 definition of collective function interface

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();

}

• Here we define the set operation interface; Collection and inherits the iterator() method of another interface Iterable. In this way, who will implement the interface later needs to implement some of the basic functions defined above; Add elements, delete elements, traverse.
• At the same time, you may notice that two generic types < e, l > are defined here, because one of our data structures is used to add elements and the other is used to add the link relationship of tree nodes.

2.6 (core) iterator function implementation

public class GroupStructure implements Collection<Employee, Link> {

    private String groupId;                                                 // The organization ID is also the head ID of an organization chain
    private String groupName;                                               // Organization name
    private Map<String, Employee> employeeMap = new ConcurrentHashMap<String, Employee>();  // Employee list
    private Map<String, List<Link>> linkMap = new ConcurrentHashMap<String, List<Link>>();  // Organizational structure and relationship; id->list
    private Map<String, String> invertedMap = new ConcurrentHashMap<String, String>();       // Reverse relation chain

    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;  // Employee ID, From
            private String toId = groupId;   // Employee ID, To

            public boolean hasNext() {
                return totalIdx < employeeMap.size();
            }

            public Employee next() {
                List<Link> links = linkMap.get(toId);
                int cursorIdx = getCursorIdx(toId);

                // Peer node scan
                if (null == links) {
                    cursorIdx = getCursorIdx(fromId);
                    links = linkMap.get(fromId);
                }

                // Parent node scan
                while (cursorIdx > links.size() - 1) {
                    fromId = invertedMap.get(fromId);
                    cursorIdx = getCursorIdx(fromId);
                    links = linkMap.get(fromId);
                }

                // Get node
                Link link = links.get(cursorIdx);
                toId = link.getToId();
                fromId = link.getFromId();
                totalIdx++;

                // Return results
                return employeeMap.get(link.getToId());
            }
             
            // Define the width traversal progress for each level
            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;
            }
        };
    }

}

• The above part of the code is a little long, mainly including the addition and deletion of elements. In addition, the most important is the implementation of traversal, new iterator < employee >.
• Adding and deleting elements are relatively simple, and two map array structures are used to define them; Employee list, organizational structure and relationship; id->list. When adding elements to the element, we will fill the pointing relationship (a - > b) into the map structure in different methods, which will build our tree organization relationship.

Implementation idea of iterator

1. In the tree structure here, what we need to do is depth traversal, that is, the one on the left goes all the way to the deepest node.
2. After traversing the deepest node, start traversing the horizontal node of the deepest node.
3. When the traversal of the horizontal node is completed, look for the horizontal node upward until all traversal of the tree structure is completed.

3. Test verification

3.1 write test class

@Test
public void test_iterator() { 
    // Data filling
    GroupStructure groupStructure = new GroupStructure("1", "Little brother Fu");  
    
    // Employee information
    groupStructure.add(new Employee("2", "tearful", "Secondary Department"));
    groupStructure.add(new Employee("3", "Bean Bun", "Secondary Department"));
    groupStructure.add(new Employee("4", "Bouncing", "Tertiary Department"));
    groupStructure.add(new Employee("5", "Big burn", "Tertiary Department"));
    groupStructure.add(new Employee("6", "Tiger brother", "Four level Department"));
    groupStructure.add(new Employee("7", "Sister Ling", "Four level Department"));
    groupStructure.add(new Employee("8", "Qiuya", "Four level Department"));   
    
    // Node Relations1 - > (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("{}，employee Id: {} Name: {}", employee.getDesc(), employee.getuId(), employee.getName());
    }
}

3.2 test results

22:23:37.166 [main] INFO  org.itstack.demo.design.test.ApiTest - Secondary department, employee Id: 2 Name: tearful
22:23:37.168 [main] INFO  org.itstack.demo.design.test.ApiTest - Level 3 Department, employee Id: 4 Name: Bouncing
22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - Level 3 Department, employee Id: 5 Name: Big burn
22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - Level 4 Department, employee Id: 6 Name: Tiger brother
22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - Level 4 Department, employee Id: 7 Name: Sister Ling
22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - Level 4 Department, employee Id: 8 Name: Qiuya
22:23:37.169 [main] INFO  org.itstack.demo.design.test.ApiTest - Secondary department, employee Id: 3 Name: Bean Bun

Process finished with exit code 0

• From the traversal results, we can see that we start traversing along the depth of the tree structure to node 3 on the right; Employee Id: 2, employee Id: 4 Employee Id: 3

6, Summary

• The design pattern of iterator can be seen from the above function implementation that it meets the single responsibility and opening and closing principle, and the external caller does not need to know the traversal differences of any different data structure in use. It can be very convenient to expand and make the whole traversal more clean and tidy.
• However, it can be seen from the implementation of the structure that the implementation process of iterator mode is relatively responsible, and the implementation of classes also expands the classes that need to be defined externally, so that the traversal is separated from the original data structure. Although this is troublesome, it can be seen that when using java jdk, the iterator mode is still very easy to use, which can be very convenient for expansion and upgrading.
• The above design pattern scenario implementation process may have some difficulties for newcomers, including; The definition of three and interfaces of iterator, the data relationship of tree structure and the idea of deep traversal of tree structure. These need repeated practice in order to deeply understand, do everything personally and personally, so that you can master these knowledge.