当前位置：网站首页>Implementation scheme of iteration and combination pattern for general tree structure

Implementation scheme of iteration and combination pattern for general tree structure

2022-06-11 23:05:00 【Wanglifeng】

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 matches 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<MenuComponent> menuComponents = new ArrayList<MenuComponent>();
    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<MenuComponent> iterator = menuComponents.iterator();
        while (iterator.hasNext()) {
            MenuComponent menuComponent = (MenuComponent) iterator.next();
            menuComponent.print();
        }
    }
}

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<GroupComponent> 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<SapoGroupRel> 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<GroupComponent> iterator = null;

    public List<GroupComponent> list = new ArrayList<GroupComponent>();

    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<GroupComponent> 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<GroupComponent> getList() {
        return list;
    }

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

    @Override
    public Iterator<GroupComponent> 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<GroupComponent> 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<GroupComponent> {

    Stack<Iterator<GroupComponent>> stack = new Stack<Iterator<GroupComponent>>();

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

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

    }

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

}

GroupIterator

public class NullIterator implements Iterator<GroupComponent> {
   
    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<GroupComponent> 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://www.cnblogs.com/wanglifeng717/p/16363485.html

原网站

版权声明
本文为[Wanglifeng]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/162/202206112254467894.html

当前位置：网站首页>Implementation scheme of iteration and combination pattern for general tree structure

Implementation scheme of iteration and combination pattern for general tree structure

边栏推荐

猜你喜欢

随机推荐