preface

Cn.hutool.core.lang. Tree

The overall function of the package source code is implemented in the package to return a common tree structure data tool code article directory outline as follows:

  • Examples of common tree data scenarios in projects

    • Summary Describes common scenarios in a project

  • Tree structure data table structure design

    • Generic data table design

  • Returns the tree structured data generic utility class

    • Validate the use of utility class code against a common tree data structure

  • The source code parsing

  • thinking

    • Why design a generic code utility class based on this scenario

Common tree data scenarios

Do after the end of the development of students should be more or less contact with tree structure data back, this scenario almost every project involved, such as the department hierarchy, commodity classification hierarchy, labels, hierarchy, and so on such scene, eventually to the user the data structure is presented by a tree structure with the file system type, see below under the intuitive feelings:

It can be seen that the department hierarchy structure in the figure above is just like a tree, with a root node and several children nodes under it, followed by children nodes. The tree structure of this level can be of infinite levels, or its level depth can be limited.

Tree structure table structure design

For the tree data scenario described above, we usually add a parentId field to the data table in daily business table design. The field value is the primary key ID of the corresponding parent node, which is used to describe the relationship between the corresponding parent and child nodes. Therefore, the general table structure can be designed as follows:

CREATE TABLE `sys_dept` (
  `id` varchar(36) NOT NULL COMMENT 'primary key ID',
  `parent_id` varchar(36) DEFAULT '0' COMMENT 'Parent ID',
  `name` varchar(255) DEFAULT ' ' COMMENT 'name',
  `weight` int(11) DEFAULT NULL COMMENT 'Weight (Sort)'.PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='Department Table';
Copy the code

Corresponding test data:

The value of parent_id is the primary key ID of the parent node. If the parent node is a root node, the value of parent_id defaults to 0, forming the following tree data structure:

  • The ministry of software
    • Java engineer
    • PHP engineer
  • Administration department
    • The financial management

Introduction to the use of tree tools

According to the above tree structure data, the general tool class is used to achieve the data query return, the test code is as follows:

public class TreeSearchTest {
	static List<TreeNode<Long>> all_menu=new ArrayList<>();
	static {
    // Construct the data source, which can be from the database query list
		all_menu.add(new TreeNode<>(1L.0L."Software Department".0L));
		all_menu.add(new TreeNode<>(2L.1L."Java Engineer".0L));
		all_menu.add(new TreeNode<>(3L.1L."PHP Engineer".0L));
		all_menu.add(new TreeNode<>(4L.0L."Administration Department".0L));
		all_menu.add(new TreeNode<>(5L.4L."Financial Management".0L));
	}

	@Test
	public void searchNode(a) {
		List<Tree<Long>> treeItems=TreeUtil.build(all_menu, 0L);

		Tree<Long> tree=treeItems.get(0);
		Tree<Long> searchResult=tree.getNode(3L);

		Assert.assertEquals("PHP Engineer", searchResult.getName()); }}Copy the code

The debugging result is as follows:

As you can see, the returned list treeItems is our common tree data structure, where children are the corresponding list of children under each node.

Tree tool class source code parsing

Tree generic return object design

Node interface, which provides node-specific method definitions

/** * node interface that provides node-specific method definitions **@param<T> ID type *@author looly
 * @since5.2.4 * /
public interface Node<T> extends Comparable<Node<T> >,Serializable {

	/** * get ID **@return ID
	 */
	T getId(a);

	/** * Set ID **@param id ID
	 * @return this
	 */
	Node<T> setId(T id);

	/** * Get the parent node ID **@returnParent node ID */
	T getParentId(a);

	/** * Sets the parent node ID **@paramParentId ID of the parent node *@return this
	 */
	Node<T> setParentId(T parentId);

	/** * Get the node label name **@returnNode label name */
	CharSequence getName(a);

	/** * Sets the node label name **@paramName Node label name *@return this
	 */
	Node<T> setName(CharSequence name);

	/** * get the weight **@returnWeight * /Comparable<? > getWeight();/** * set the weight **@paramWeight weight *@return this
	 */
	Node<T> setWeight(Comparable
        weight);

	@SuppressWarnings({"unchecked", "rawtypes", "NullableProblems"})
	@Override
	default int compareTo(Node node) {
		final Comparable weight = this.getWeight();
		if (null! = weight) {final Comparable weightOther = node.getWeight();
			return weight.compareTo(weightOther);
		}
		return 0; }}Copy the code
  • The main is to abstract out the common field methods of each node, generally there will beid,parent_id,name,weightGeneral field, etc.

The final returned tree entity object

/** * Convert your entities to TreeNodeMap nodes via the converter@param<T> ID type *@author liangbaikai
 * @since5.2.1 * /
public class Tree<T> extends LinkedHashMap<String.Object> implements Node<T> {
	private static final long serialVersionUID = 1L;

	private final TreeNodeConfig treeNodeConfig;
	private Tree<T> parent;

	public Tree(a) {
		this(null);
	}

	/** * construct **@paramTreeNodeConfig TreeNode configuration */
	public Tree(TreeNodeConfig treeNodeConfig) {
		super(a);this.treeNodeConfig = ObjectUtil.defaultIfNull(
				treeNodeConfig, TreeNodeConfig.DEFAULT_CONFIG);
	}

	/** * get the parent node **@returnThe parent node *@since5.2.4 * /
	public Tree<T> getParent(a) {
		return parent;
	}

	/** * get the node with the same ID. If there are multiple nodes with the same ID, return only the first node. <br> * This method finds only this node and its children, using breadth-first traversal. * *@param id ID
	 * @returnNode *@since5.2.4 * /
	public Tree<T> getNode(T id) {
		return TreeUtil.getNode(this, id);
	}

	/** * get the list of all parent node names ** <p> * For example, if there is a person in r&d 1, he has r&d department above him, then the technology center above him <br> * The result is: r&d department, R&D center, technology center **@paramId Node ID *@paramIncludeCurrentNode whether to include the name of the current node *@returnList of all parent node names *@since5.2.4 * /
	public List<CharSequence> getParentsName(T id, boolean includeCurrentNode) {
		return TreeUtil.getParentsName(getNode(id), includeCurrentNode);
	}

	/** * get the list of all parent node names ** <p> * For example, if there is a person in r&d 1, he has r&d department above him, then the technology center above him <br> * The result is: r&d department, R&D center, technology center **@paramIncludeCurrentNode whether to include the name of the current node *@returnList of all parent node names *@since5.2.4 * /
	public List<CharSequence> getParentsName(boolean includeCurrentNode) {
		return TreeUtil.getParentsName(this, includeCurrentNode);
	}

	/** * sets the parent node **@paramParent Parent node *@return this
	 * @since5.2.4 * /
	public Tree<T> setParent(Tree<T> parent) {
		this.parent = parent;
		if (null! = parent) {this.setParentId(parent.getId());
		}
		return this;
	}

	@Override
	@SuppressWarnings("unchecked")
	public T getId(a) {
		return (T) this.get(treeNodeConfig.getIdKey());
	}

	@Override
	public Tree<T> setId(T id) {
		this.put(treeNodeConfig.getIdKey(), id);
		return this;
	}

	@Override
	@SuppressWarnings("unchecked")
	public T getParentId(a) {
		return (T) this.get(treeNodeConfig.getParentIdKey());
	}

	@Override
	public Tree<T> setParentId(T parentId) {
		this.put(treeNodeConfig.getParentIdKey(), parentId);
		return this;
	}

	@Override
	public CharSequence getName(a) {
		return (CharSequence) this.get(treeNodeConfig.getNameKey());
	}

	@Override
	public Tree<T> setName(CharSequence name) {
		this.put(treeNodeConfig.getNameKey(), name);
		return this;
	}

	@Override
	publicComparable<? > getWeight() {return(Comparable<? >)this.get(treeNodeConfig.getWeightKey());
	}

	@Override
	public Tree<T> setWeight(Comparable
        weight) {
		this.put(treeNodeConfig.getWeightKey(), weight);
		return this;
	}

	@SuppressWarnings("unchecked")
	public List<Tree<T>> getChildren() {
		return (List<Tree<T>>) this.get(treeNodeConfig.getChildrenKey());
	}

	public void setChildren(List<Tree<T>> children) {
		this.put(treeNodeConfig.getChildrenKey(), children);
	}

	/** * Extension attributes **@paramThe key key *@paramValue Extended value */
	public void putExtra(String key, Object value) {
		Assert.notEmpty(key, "Key must be not empty !");
		this.put(key, value); }}Copy the code
  • Inherited fromLinkedHashMap<String, Object>Object, mainly for the definition of field name flexibility, at the same time the expansion will be better, in the source code can also see aputExtraMethod is used to return extended attributes
  • To achieve theNode<T>Node interface, indicating that the modified class is a node entity class containing the common field methods of the node
  • Constructors can be passed inTreeNodeConfigObject initializes the node configuration class of the current node entity class, which is used to dynamically inject node field names when each field is fetched or set. If not, the constructor uses the defaultTreeNodeConfig.DEFAULT_CONFIGThe default field name is used as follows: 
     // Attribute name configuration field
  private String idKey = "id";
  private String parentIdKey = "parentId";
  private String weightKey = "weight";
  private String nameKey = "name";
  private String childrenKey = "children";
Copy the code

Abstract data source objects transform tree objectsTreeInterface converter

Usually we write your own generated tree object, will first to convert the data source object list of tile to return to the tree structure of objects list, in here to switch the logic abstract functional interface, the source code provided in the default converter implementation, of course, we also can custom implement this interface at any time

/** * tree node parsers can refer to {@link DefaultNodeParser}
 *
 * @param<T> Converts the entity to the object type * in the data source@author liangbaikai
 */
@FunctionalInterface
public interface NodeParser<T.E> {
	/ * * *@paramObject Source data entity *@paramTreeNode treeNode entity */
	void parse(T object, Tree<E> treeNode);
}
Copy the code

The default converter is as follows, using the default field name for the conversion logic and setting some extended property fields

/** * The default simple converter **@param<T> ID type *@author liangbaikai
 */
public class DefaultNodeParser<T> implements NodeParser<TreeNode<T>, T> {

	@Override
	public void parse(TreeNode<T> treeNode, Tree<T> tree) {
    // Conversion Settings for some tree generic fields
		tree.setId(treeNode.getId());
		tree.setParentId(treeNode.getParentId());
		tree.setWeight(treeNode.getWeight());
		tree.setName(treeNode.getName());

		// Extend the field
		final Map<String, Object> extra = treeNode.getExtra();
		if(MapUtil.isNotEmpty(extra)){ extra.forEach(tree::putExtra); }}}Copy the code

The tree data list returns the final entry

/** * tree construction **@param<T> Converts the entity to the object type * in the data source@param<E> ID type *@paramList Source data set *@paramParentId the value of the parentId of the uppermost level is usually 0 or *@paramTreeNodeConfig configuration *@paramNodeParser converter *@return List
	 */
	public static <T, E> List<Tree<E>> build(List<T> list, E parentId, TreeNodeConfig treeNodeConfig, NodeParser<T, E> nodeParser) {
		//1. First convert the source data list to the final returned Tree data object entity Tree
		final List<Tree<E>> treeList = CollUtil.newArrayList();
		Tree<E> tree;
		for (T obj : list) {
      // Initializes the tree node object, passing in the node configuration object
			tree = new Tree<>(treeNodeConfig);
      // Use custom converters to convert objects
			nodeParser.parse(obj, tree);
      // Put the converted data object into the list
			treeList.add(tree);
		}

    // Initializes the list of tree nodes that are eventually returned
		List<Tree<E>> finalTreeList = CollUtil.newArrayList();
    // Traverses the tree node list, recursively assembles the tree data, and supports the nodes in each node list to be sorted according to the weight
		for (Tree<E> node : treeList) {
			if (ObjectUtil.equals(parentId,node.getParentId())) {
				finalTreeList.add(node);
				innerBuild(treeList, node, 0, treeNodeConfig.getDeep()); }}// Each layer of memory has been sorted by the outermost layer
		finalTreeList = finalTreeList.stream().sorted().collect(Collectors.toList());
		return finalTreeList;
	}
Copy the code
  • The source data list is first transformed into the final returned tree data object entityTree, the transformation process uses customizable node configuration objectsTreeNodeConfigAnd customNodeParserconverter
  • Node parameters can be processed at the root levelparentIdGenerally, this parameter is passed according to the value defined by the business, such as the value of the root node of the business table designparentIdIs defined as0, the parameter is passed0
  • The tree node list is traversed to assemble tree data recursively, and the nodes in the node list of each layer are sorted according to the weight

Recursive generation node method

/ * * * * * recursive processing@paramTreeNodes data set *@paramParentNode Current node *@paramDeep The recursive depth *@paramMaxDeep may have a maximum recursion depth of NULL, i.e. */ is not limited
	private static <T> void innerBuild(List<Tree<T>> treeNodes, Tree<T> parentNode, int deep, Integer maxDeep) {

		if (CollUtil.isEmpty(treeNodes)) {
			return;
		}
		//maxDeep may be empty
		if(maxDeep ! =null && deep >= maxDeep) {
			return;
		}

		// TreeNodeMap implements the Comparable interface
		treeNodes = treeNodes.stream().sorted().collect(Collectors.toList());
		for (Tree<T> childNode : treeNodes) {
			if (parentNode.getId().equals(childNode.getParentId())) {
				List<Tree<T>> children = parentNode.getChildren();
				if (children == null) {
					children = CollUtil.newArrayList();
					parentNode.setChildren(children);
				}
				children.add(childNode);
// childNode.setParentId(parentNode.getId());
				childNode.setParent(parentNode);
				innerBuild(treeNodes, childNode, deep + 1, maxDeep); }}}Copy the code

Consider: Why design a generic code utility class based on this scenario

  • Code reusability: Programmers who don’t want to be lazy are bad coders, and the code for common data scenarios only needs to be written once

  • Reuse the existing tool class code, dealing with various types of tree structure data appears more convenient, higher fault tolerance rate

The last

I wish you all a happy and prosperous year of the Ox in 2021.

Reference:

  • HutoolWebsite:hutool.cn/
  • github:Github.com/looly/hutoo…

More original articles will be pushed in the public account at the first time, welcome to scan the code to follow Zhang Shaolin