将实体列表转换为JTree模型

Question

我们从数据库中获取一个列表，需要将其转换为

JTree

。诀窍是建立一个模型。

规则：

1. 每条记录都有

   ID

   以及

   ROOT_ID

   。
2. 如果一条记录的

   ROOT_ID

   与另一条记录的

   ID

   匹配，则它是该记录的子记录。

3. ROOT_ID

   与列表中任何

   KEYID

   都不匹配的记录是根（

   ROOT_ID

   可能是

   null

   ）。
4. 虽然我不会把我的生命押在它上面，但您可以假设实体集合中只有一个根记录（我与分析师核实过，我可以不显示后续根（如果存在））。

我幼稚的方法并不是很有效，因为它是

O(n²)

。

您的目标是编写时间复杂度更好的

fill()

方法的替代实现。尽量不要让代码完全不可读（软要求）。

Java 8、Apache Commons 2.6、Apache Collections 3.2.2。

import org.junit.jupiter.api.Test;

import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.DefaultTreeModel;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

public class TreeTest {

    @Test
    public void fill_givenModel_loadsBuildsAndLinksNodesInExpectedWay() {
        DefaultTreeModel model = new DefaultTreeModel(null);
        fill(model);
        /*
        I won't write space-intensive, time-consuming asserts, 
        but you can see if the model's correct in the debugger:
        
        What I expect:
        2
        |_3
          |_1
            |_10
          |_15
        |_22
          |_6
          |_5
         */
    } // set breakpoint here

    void fill(DefaultTreeModel model) {
        List<DefaultMutableTreeNode> nodes = buildNodes();
        for (DefaultMutableTreeNode node : nodes) {
            TreeEntity currentEntity = (TreeEntity) node.getUserObject();
            Object currentKey = currentEntity.getId();
            for (DefaultMutableTreeNode n : nodes) {
                TreeEntity ce = (TreeEntity) n.getUserObject();
                boolean isChild = areNumericallyEqual(ce.getRootId(), currentKey);
                if (isChild) node.add(n);
            }
        }
        findRoot(nodes).ifPresent(model::setRoot);
    }

    private List<DefaultMutableTreeNode> buildNodes() {
        // imagine I actually load it from a DB
        List<TreeEntity> entities = Arrays.asList(
                new TreeEntity(6, 22),
                new TreeEntity(1, 3),
                new TreeEntity(3, 2),
                new TreeEntity(2, 99),
                new TreeEntity(22, 2),
                new TreeEntity(5, 22),
                new TreeEntity(10, 1),
                new TreeEntity(15, 3)
        );
        return entities.stream()
                .map(DefaultMutableTreeNode::new)
                .collect(Collectors.toList());
    }

    private boolean areNumericallyEqual(Object firstValue, Object secondValue) {
        // in the real scenario, it could be any type, so we have a similar utility method in our codebase
        // except it does parsing in case the value is a string
        Optional<Double> firstDoubleOptional = asDouble(firstValue);
        Optional<Double> secondDoubleOptional = asDouble(secondValue);
        return firstDoubleOptional.equals(secondDoubleOptional);
    }

    private static Optional<Double> asDouble(Object firstValue) {
        Optional<Double> firstDoubleOptional = Optional.ofNullable(firstValue)
                .filter(v -> v instanceof Number)
                .map(Number.class::cast)
                .map(Number::doubleValue);
        return firstDoubleOptional;
    }

    private Optional<DefaultMutableTreeNode> findRoot(List<DefaultMutableTreeNode> nodes) {
        return nodes.stream().filter(DefaultMutableTreeNode::isRoot).findFirst();
    }

    /**
     * A simplistic entity with only essential fields.
     */
    static class TreeEntity {
        private final Integer id;
        private final Integer rootId;

        TreeEntity(Integer id, Integer rootId) {
            this.id = id;
            this.rootId = rootId;
        }

        public Integer getId() {
            return id;
        }

        public Integer getRootId() {
            return rootId;
        }

        @Override
        public String toString() {
            return String.valueOf(id);
        }
    }
}

Answer 1

这有点像家庭作业，因此只有这种方法。

创建所有节点：

• 没有链接到其 ROOT_ID 的节点
• 在从 ID 到节点的 Map 中。

= 复杂度 O(N * log N)：N 个节点的一个循环，每次插入最多花费 O(log N)。

现在走过地图，并为每个节点在地图上填写其 ROOT_ID 节点。

= 复杂度 O(N *log N)：N 个节点的一个循环，每次地图检索最多 O(log N)。

这使得总复杂度为 O(N * log N)。

您所做的是提前创建尚未填充的元素，因此您可以在第二阶段中从每个元素引用它们。