Implementation scheme of iteration and combination pattern for general tree structure

High quality resource sharing

Learning route guidance （ Click unlock ）	Knowledge orientation	Crowd positioning
🧡 Python Actual wechat ordering applet 🧡	Progressive class	This course is python flask+ Perfect combination of wechat applet , From the deployment of Tencent to the launch of the project , Create a full stack ordering system .
Python Quantitative trading practice	beginner	Take you hand in hand to create an easy to expand 、 More secure 、 More efficient quantitative trading system

During the daily development process . Tree structure is used very frequently .

for example ： Company structure 、 Various classification structures 、 Grouping structure, etc .

SET FOREIGN\_KEY\_CHECKS = 0;

CREATE TABLE IF NOT EXISTS `tbl\_sapo\_group` (
 `id` int(10) unsigned NOT NULL AUTO\_INCREMENT COMMENT ' Primary key ',
 `code` varchar(100) NOT NULL COMMENT ' Unique code ',
 `create\_time` datetime(3) NOT NULL COMMENT ' Creation time ',
 `last\_update\_time` datetime(3) DEFAULT NULL COMMENT ' Last update time ',
 `name` varchar(255) NOT NULL COMMENT ' name ',
 `detail` varchar(255) DEFAULT NULL COMMENT ' details ',
 `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT ' state :0- Invalid ,1- It works ,2- edit ',
 `group\_type` varchar(100) NOT NULL COMMENT ' Group type ',
 PRIMARY KEY (`id`),
 UNIQUE KEY `uni\_idx\_group\_code` (`code`),
 KEY `idx\_group\_group\_type` (`group\_type`),
 CONSTRAINT `fk\_group\_group\_type` FOREIGN KEY (`group\_type`) REFERENCES `tbl\_sapo\_group\_type` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT=' Group ';

CREATE TABLE IF NOT EXISTS `tbl\_sapo\_group\_rel` (
 `id` int(10) unsigned NOT NULL AUTO\_INCREMENT COMMENT ' Primary key ',
 `create\_time` datetime(3) NOT NULL COMMENT ' Creation time ',
 `last\_update\_time` datetime(3) DEFAULT NULL COMMENT ' Last update time ',
 `parent\_code` varchar(100) NOT NULL COMMENT ' Parent node code ,tbl\_sapo\_group surface code',
 `child\_code` varchar(100) NOT NULL COMMENT ' Child node code ,tbl\_sapo\_group surface code',
 `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT ' state :0- Invalid ,1- It works ,2- edit ',
 `group\_rel\_type` varchar(100) NOT NULL COMMENT ' Group relationship type code , come from tbl\_sapo\_group\_rel\_type surface code',
 `tree\_code` varchar(100) NOT NULL COMMENT ' Tree node code ,tbl\_sapo\_tree surface code',
 PRIMARY KEY (`id`),
 KEY `idx\_group\_rel\_child\_code` (`child\_code`),
 KEY `idx\_group\_rel\_parent\_code` (`parent\_code`),
 KEY `idx\_group\_rel\_group\_rel\_type` (`group\_rel\_type`),
 KEY `idx\_group\_rel\_tree\_code\_status\_parent\_code\_child\_code` (`tree\_code`,`status`,`parent\_code`,`child\_code`),
 CONSTRAINT `fk\_group\_rel\_child\_code` FOREIGN KEY (`child\_code`) REFERENCES `tbl\_sapo\_group` (`code`),
 CONSTRAINT `fk\_group\_rel\_group\_rel\_type` FOREIGN KEY (`group\_rel\_type`) REFERENCES `tbl\_sapo\_group\_rel\_type` (`code`),
 CONSTRAINT `fk\_group\_rel\_parent\_code` FOREIGN KEY (`parent\_code`) REFERENCES `tbl\_sapo\_group` (`code`),
 CONSTRAINT `fk\_group\_rel\_tree\_code` FOREIGN KEY (`tree\_code`) REFERENCES `tbl\_sapo\_tree` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT=' Group relationship ';

CREATE TABLE IF NOT EXISTS `tbl\_sapo\_group\_rel\_type` (
 `id` int(10) unsigned NOT NULL AUTO\_INCREMENT COMMENT ' Primary key ',
 `code` varchar(100) NOT NULL COMMENT ' Unique code ',
 `create\_time` datetime(3) NOT NULL COMMENT ' Creation time ',
 `last\_update\_time` datetime(3) DEFAULT NULL COMMENT ' Last update time ',
 `name` varchar(255) NOT NULL COMMENT ' name ',
 `detail` varchar(255) DEFAULT NULL COMMENT ' details ',
 `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT ' state :0- Invalid ,1- It works ,2- edit ',
 PRIMARY KEY (`id`),
 UNIQUE KEY `uni\_idx\_group\_rel\_type\_code` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT=' Group relationship type ';

CREATE TABLE IF NOT EXISTS `tbl\_sapo\_group\_type` (
 `id` int(10) unsigned NOT NULL AUTO\_INCREMENT COMMENT ' Primary key ',
 `code` varchar(100) NOT NULL COMMENT ' Unique code ',
 `create\_time` datetime(3) NOT NULL COMMENT ' Creation time ',
 `last\_update\_time` datetime(3) DEFAULT NULL COMMENT ' Last update time ',
 `name` varchar(255) NOT NULL COMMENT ' name ',
 `detail` varchar(255) DEFAULT NULL COMMENT ' details ',
 `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT ' state :0- Invalid ,1- It works ,2- edit ',
 PRIMARY KEY (`id`),
 UNIQUE KEY `uni\_idx\_group\_type\_code` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT=' Group type ';

CREATE TABLE IF NOT EXISTS `tbl\_sapo\_tree` (
 `id` int(10) unsigned NOT NULL AUTO\_INCREMENT COMMENT ' Primary key ',
 `code` varchar(100) NOT NULL COMMENT ' Unique code ',
 `create\_time` datetime(3) NOT NULL COMMENT ' Creation time ',
 `last\_update\_time` datetime(3) DEFAULT NULL COMMENT ' Last update time ',
 `name` varchar(255) NOT NULL COMMENT ' name ',
 `detail` varchar(255) DEFAULT NULL COMMENT ' details ',
 `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT ' state :0- Invalid ,1- It works ,2- edit ',
 PRIMARY KEY (`id`),
 UNIQUE KEY `uni\_idx\_tree\_code` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT=' Tree definition ';

CREATE TABLE IF NOT EXISTS `tbl\_sapo\_tree\_group` (
 `id` int(10) unsigned NOT NULL AUTO\_INCREMENT COMMENT ' Primary key ',
 `create\_time` datetime(3) NOT NULL COMMENT ' Creation time ',
 `last\_update\_time` datetime(3) DEFAULT NULL COMMENT ' Last update time ',
 `group\_code` varchar(100) NOT NULL COMMENT ' Group code ,tbl\_sapo\_group surface code',
 `tree\_code` varchar(100) NOT NULL COMMENT ' Tree code ,tbl\_sapo\_tree surface code',
 `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT ' state :0- Invalid ,1- It works ,2- edit ',
 `is\_root` int(10) unsigned DEFAULT NULL COMMENT ' Whether the root node :1- The root node ,null Non root node ',
 PRIMARY KEY (`id`),
 UNIQUE KEY `uni\_idx\_tree\_group\_tree\_code\_is\_root` (`tree\_code`,`is\_root`),
 KEY `idx\_tree\_group\_group\_code` (`group\_code`),
 CONSTRAINT `fk\_tree\_group\_group\_code` FOREIGN KEY (`group\_code`) REFERENCES `tbl\_sapo\_group` (`code`),
 CONSTRAINT `fk\_tree\_group\_tree\_code` FOREIGN KEY (`tree\_code`) REFERENCES `tbl\_sapo\_tree` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT=' Groups contained in the tree ';

SET FOREIGN\_KEY\_CHECKS = 1;

Create table statement
As shown in the figure, the relational database model , It basically meets the requirements of multiple trees in a system 、 The purpose for which groups can be reused .

The node of the tree may be a single node , It may also be the root of a subtree . When we need to traverse, we need different processing from different nodes , Use 【 polymorphic 】.

But don't distinguish which node it is when processing , Provide a kind of 【 Transparency 】 Processing mode , To implement, you need to reference two patterns ： Iterative mode 、 Portfolio model

Old rules , First introduce the concept , After that .

| Iterator pattern | Provides a way to traverse a collection without exposing its implementation |
| Portfolio model | Customers can treat collections of objects as well as individual objects equally |

Iterator pattern ：

|
 
  | Iterator example ： Array implementation iterator

//  Iterator interface 
interface Iterator {
 boolean hasNext();

 Object next();
}

//  A menu item 
class MenuItem {

 String name;
 String description;
 boolean vegetarian;
 double price;

 public MenuItem(String name, String description, boolean vegetarian, double price) {
 this.name = name;
 this.description = description;
 this.vegetarian = vegetarian;
 this.price = price;
 }
 // getter,setter Method 
    public String getName() {
 return name;
 }
}

//  menu 
class DinerMenu {
 static final int MAX\_ITEMS = 6;
 int numberOfItems = 0;
 MenuItem[] menuItems;

 public DinerMenu() {
 menuItems = new MenuItem[MAX\_ITEMS];
 addItem(" Stewed Pork Ball in Brown Sauce ", " Jiangnan famous dishes ", true, 50d);
 addItem(" Pork Lungs in Chili Sauce ", " It has nothing to do with husband and wife ", true, 70d);
 }

 public void addItem(String name, String description, boolean vegetarian, double price) {
 MenuItem menuItem = new MenuItem(name, description, vegetarian, price);
 if (numberOfItems >= MAX\_ITEMS) {
 System.out.println("sorry,menu is full");
 } else {
 menuItems[numberOfItems] = menuItem;
 numberOfItems += 1;
 }
 }

 public MenuItem[] getMenuItems() {
 return menuItems;
 }

 public Iterator createIteator() {
 return new DinerMenuIterator(menuItems);
 }
}

class DinerMenuIterator implements Iterator {
 MenuItem[] items;
 int position = 0;

 public DinerMenuIterator(MenuItem[] items) {
 this.items = items;
 }

 public Object next() {
 MenuItem menuItem = items[position];
 position = position + 1;
 return menuItem;
 }

 public boolean hasNext() {
 //  The array may not be full 
        if (position >= items.length || items[position] == null) {
 return false;
 } else {
 return true;
 }
 }

 public void remove() {
 if (position <= 0) {
 throw new IllegalStateException("you can't an item unitl you've done at least on next()");
 }
 if (items[position - 1] != null) {
 for (int i = position - 1; i < (items.length - 1); i++) {
 items[i] = items[i + 1];
 }
 items[items.length - 1] = null;
 }

 }

}

//  test 
class Test {
 public static void main(String[] args) {
 Iterator iterator = (new DinerMenu()).createIteator();
 while(iterator.hasNext()){
 MenuItem menuItem = (MenuItem) iterator.next();
 System.out.println(menuItem.getName());
 }

 }
}
 Example iterator pattern 

Array iterator
1. Of course remove Can not be realized , Because it may be concurrent remove, Iterators are unsafe .
We simply deal with throwing java.lang.UnsupportedOperationException
2.java5 after , Collections can be used for/in The form replaces the creation iterator shown .
for( Object obj: collection){
} |

For different sets , We have different traversal methods . Is there a general pattern for traversing collections , Shield this difference , This pattern is the iterator .

The iterator pattern provides a way to access the elements of an aggregate object sequentially , Without exposing its internal representation .

In fact, it's plain , The iterator pattern is defined by defining a unified operation interface , To shield different underlying operating logic .

If you can have a unified method to access every object in the aggregation , You can write polymorphic code to match these aggregations .

Put the wandering task on the iterator , Instead of aggregating . This simplifies the interface and implementation of aggregation . Clear distribution of responsibilities .

accord with 【 Single responsibility 】, If you do not use the iterator pattern , If the set changes , For example, from a set to an array , This class must be changed , The traversal mode also changes .

Portfolio model ：

Allows you to combine objects into a tree structure to represent “ whole / part ” hierarchy .

Composition allows customers to handle individual objects and composition of objects in a consistent way . That is, we can ignore the differences between object combinations and individual objects , Use the same operation .

Composite mode sacrifice 【 Single responsibility 】 obtain 【 transparency 】, Transparency means that customer processing combinations and leaf nodes are treated equally . Whether a node is a combination or a leaf node , Transparent to customers .

|
 
 
 
  | Examples of combination patterns ：

public abstract class MenuComponent {
 
 //  Operation nodes require methods 
    public void add(MenuComponent menuComponent) {
 throw new UnsupportedOperationException();
 }
 public void remove(MenuComponent menuComponent) {
 throw new UnsupportedOperationException();
 }
 public MenuComponent getChild(int i) {
 throw new UnsupportedOperationException();
 }
 
 //  The menu itself 
    public String getName() {
 throw new UnsupportedOperationException();
 }
 public String getDescription() {
 throw new UnsupportedOperationException();
 }
 public double getPrice() {
 throw new UnsupportedOperationException();
 }
 public boolean isVegetarian() {
 throw new UnsupportedOperationException();
 }
 
 public void print() {
 throw new UnsupportedOperationException();
 }
}

MenuComponent

public class Menu extends MenuComponent {
 ArrayList menuComponents = new ArrayList();
 String name;
 String description;

 public Menu(String name, String description) {
 this.name = name;
 this.description = description;
 }

 public void add(MenuComponent menuComponent) {
 menuComponents.add(menuComponent);
 }

 public void remove(MenuComponent menuComponent) {
 menuComponents.remove(menuComponent);
 }

 public MenuComponent getChild(int i) {
 return (MenuComponent) menuComponents.get(i);
 }

 public String getName() {
 return name;
 }

 public String getDescription() {
 return description;
 }

 public void print() {
 System.out.print("\n" + getName());
 System.out.println(", " + getDescription());
 System.out.println("---------------------");

 Iterator iterator = menuComponents.iterator();
 while (iterator.hasNext()) {
 MenuComponent menuComponent = (MenuComponent) iterator.next();
 menuComponent.print();
 }
 }
}

Menu

public class MenuItem extends MenuComponent {
 String name;
 String description;
 boolean vegetarian;
 double price;
 
 public MenuItem(String name, 
 String description, 
 boolean vegetarian, 
 double price) 
 { 
 this.name = name;
 this.description = description;
 this.vegetarian = vegetarian;
 this.price = price;
 }
 
 public String getName() {
 return name;
 }
 
 public String getDescription() {
 return description;
 }
 
 public double getPrice() {
 return price;
 }
 
 public boolean isVegetarian() {
 return vegetarian;
 }
 
 public void print() {
 System.out.print("  " + getName());
 if (isVegetarian()) {
 System.out.print("(v)");
 }
 System.out.println(", " + getPrice());
 System.out.println("     -- " + getDescription());
 }
}

MenuItem

public class Waitress {
 MenuComponent allMenus;
 
 public Waitress(MenuComponent allMenus) {
 this.allMenus = allMenus;
 }
 
 public void printMenu() {
 allMenus.print();
 }
}

Waitress
  |

Example ：

Use iteration and composition patterns to implement a common tree structure ：

1. Core and group to group relationships .

2. The scheme was implemented , Internal iterators and external iterators . Use according to the actual situation .

|
 
  |
 
  |

public abstract class GroupComponent {

 

 public abstract Iterator createIterator();
 
 //  The first line of characters is a few spaces empty 
 protected abstract String printTreeStr(int i);
 
 public abstract String getName();
 
 public String printTreeStr() {
 return printTreeStr(0);
 };
 
 
 
 //  Print tree solution structure 
 protected String padding\_n(int n) {
 StringBuffer space = new StringBuffer("");
 for (int i = 0; i < n; i++) {
 space.append("-");
 }
 space.append("|");
 return space.toString();
 }
 
 //  Get the tree structure recursively 
 public static GroupComponent getTree(String groupCode) {
 //  Get general dao
 CommonDao dao = SpringUtil.getBean(CommonDao.class);
 //  Group details in the database model class 
 SapoGroup sapoGroup = dao.getObj(SapoGroup.getInstance().setCode(groupCode));

 //  Query all the sons of this node 
 List childList = dao.getObjListWithEmpty(SapoGroupRel.getInstance().setParentCode(groupCode));

 //  If there are no child nodes , Directly create a new leaf node and return 
 if (childList == null || childList.size() == 0) {
 LeafGroup leafGroup = new LeafGroup();
 leafGroup.setLeafGroup(sapoGroup);
 return leafGroup;
 } else {
 //  If there are child nodes 
 Group group = new Group();
 group.setGroupDetail(sapoGroup);
 for (SapoGroupRel rel : childList) {
 //  Recursively get the previous node 
 GroupComponent child = getTree(rel.getChildCode());
 group.getList().add(child);
 }
 return group;
 }
 }
}

GroupComponent

public class Group extends GroupComponent {

 Iterator iterator = null;

 public List list = new ArrayList();

 public SapoGroup groupDetail;

 public SapoGroup getGroupDetail() {
 return groupDetail;
 }

 public void setGroupDetail(SapoGroup groupDetail) {
 this.groupDetail = groupDetail;
 }

 /*
 *  Print tree hierarchy 
 */
 protected String printTreeStr(int i) {
 //  Fields to be printed 
 String waitPrintStr = this.groupDetail.getName();

 StringBuilder sb = new StringBuilder();
 sb.append(padding\_n(i));
 sb.append(waitPrintStr);
 sb.append("\r\n");

 Iterator iterator = list.iterator();

 while (iterator.hasNext()) {
 GroupComponent next = iterator.next();
 //  Recursive traversal 
 String printTree = next.printTreeStr(i + 2);
 sb.append(printTree);
 }
 return sb.toString();
 }

 public List getList() {
 return list;
 }

 public void setList(List list) {
 this.list = list;
 }

 @Override
 public Iterator createIterator() {
 if (iterator == null) {
 iterator = new GroupIterator(list.iterator());
 }
 return iterator;
 }

 @Override
 public String getName() {

 return "list: " + groupDetail.getName();
 }

}

Group

public class LeafGroup extends GroupComponent {

 private SapoGroup leafGroup;

 public SapoGroup getLeafGroup() {
 return leafGroup;
 }

 public void setLeafGroup(SapoGroup leafGroup) {
 this.leafGroup = leafGroup;
 }

 public Iterator createIterator() {
 return new NullIterator();
 }

 protected String printTreeStr(int i) {
 //  Key fields 
 String waitPrintStr = this.getLeafGroup().getName();
 return padding\_n(i) + waitPrintStr + "\r\n";
 }

 /* (non-Javadoc)
 * @see cn.com.fmsh.nfcos.sapo.biz.testGroup.GroupComponent#getName()
 */
 @Override
 public String getName() {
 return "leaf: "+leafGroup.getName();
 }

}

LeafGroup

public class GroupIterator implements Iterator {

 Stack> stack = new Stack>();

 public GroupIterator(Iterator iterator) {
 stack.push(iterator);
 }

 public boolean hasNext() {
 if (stack.isEmpty()) {
 return false;
 } else {
 Iterator iterator = stack.peek();
 if (!iterator.hasNext()) {
 stack.pop();
 return hasNext();
 } else {
 return true;
 }
 }

 }

 
 public GroupComponent next() {
 if(hasNext()) {
 Iterator iterator = stack.peek();
 GroupComponent next = iterator.next();
 stack.push(next.createIterator());
 return next;
 }else {
 return null;
 } 
 }

}

GroupIterator

public class NullIterator implements Iterator {
 
 public GroupComponent next() {
 return null;
 }
 
 public boolean hasNext() {
 return false;
 }
 
 
}

NullIterator

The test program , Traverse the tree structure 、 Print tree structure .

 @Test
 public void Test() {

 //  Use an external iterator to traverse 
        GroupComponent tree = Group.getTree("hotel");

 Iterator iterator = tree.createIterator();

 while (iterator.hasNext()) {
 GroupComponent next = iterator.next();
 // TODO  Traverse the operation contents 

 }

 System.out.println("---- Print tree structure -----");
 
 //  Print tree structure 
 System.err.println(GroupComponent.getTree("hotel").printTreeStr());

 }

This article is from the blog Garden , author ：wanglifeng, Reprint please indicate the original link ：https://blog.csdn.net/wanglifeng717/p/16363485.html