Converting entity list into JTree model

We get a list from DB that we need to convert into a JTree. The trick is to build a model.

The rules:

1. Each record has ID as well as ROOT_ID.
2. If a record's ROOT_ID matches another record's ID, it's a child of that record.
3. The record whose ROOT_ID doesn't match any KEYID in the list is a root (ROOT_ID may be null).
4. While I won't bet my life on it, you can assume there's only one root record in the entity collection (I checked with the analyst, I can get away with not displaying subsequent roots, if present).

My naïve approach is not very efficient as it's O(n²).

Your goal is to write an alternative implementation of the fill() method whose time complexity is better. Try not to make the code totally unreadable (soft requirement).

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

This reeks a bit of home work, hence only the approach.

Create all nodes:

• without link to their ROOT_ID's node
• in a Map from ID to node.

= Complexity O(N * log N): one loop of N nodes with every insertion costing at most O(log N).

Now walk over the map and for every node fill in its ROOT_ID's node by the map.

= Complexity O(N *log N): one loop of N nodes with every map retrieval at most O(log N).

That makes the total complexity O(N * log N). A HashMap will generally be faster than O(log N).

What you are doing is creating the elements in advance, still unfilled, so you can refer to them from every element in a second stage.