Sort a list with a parent reference like a tree

Question

Situation

I have an unordered list with data objects, each object has a reference to its parent. The list should be sorted by reference to parent and the final list should be in the order as if it were a tree. The children should be ordered by name.

The data object:

/**
 * Object with a parent relationship 
 */
public static class Node {

    Node parent;
    String text;
    int level = -1;

    public Node(Node parent, String text) {
        this.parent = parent;
        this.text = text;
    }

    public String toString() {
        return text;
    }
}

An example tree:

/**
 * Create example data
 * @return
 */
private static List<Node> createExampleList() {

    List<Node> list = new ArrayList<>();

    Node root = new Node(null, "root");

    Node a = new Node(root, "a");
    Node b = new Node(root, "b");
    Node c = new Node(root, "c");

    Node a1 = new Node(a, "a1");
    Node a2 = new Node(a, "a2");
    Node a3 = new Node(a, "a3");

    Node b1 = new Node(b, "b1");
    Node b2 = new Node(b, "b2");
    Node b3 = new Node(b, "b3");

    Node c1 = new Node(c, "c1");
    Node c2 = new Node(c, "c2");
    Node c3 = new Node(c, "c3");


    Node b11 = new Node(b1, "b11");
    Node b12 = new Node(b1, "b12");
    Node b13 = new Node(b1, "b13");


    list.add(root);

    list.add(a);
    list.add(b);
    list.add(c);

    list.add(a1);
    list.add(a2);
    list.add(a3);

    list.add(b1);
    list.add(b11);
    list.add(b12);
    list.add(b13);

    list.add(b2);
    list.add(b3);

    list.add(c1);
    list.add(c2);
    list.add(c3);

    return list;
}

Problem

My current solution is heavy on the memory. The algorithm I have so far:

• create a DefaultMutableTreeNode for every object and put it into a map
• iterate through all objects, get the object's and the parent's DefaultMutableTreeNode representation and add the node to the parent
• use the enumeration mechanisms of DefaultMutableTreeNode to traverse the tree and add each item to the list iteratively

Question

Does anyone know a faster and more memory efficient way?

Code

Here's the code I have so far:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import javax.swing.tree.DefaultMutableTreeNode;

/**
 * Sort a list of parent-child related items. The resulting list should be ordered as if the list were a tree. 
 * The algorithm converts the list to an intermediary tree using {@link DefaultMutableTreeNode} as a wrapper.
 * That way you can create the final list depending on your needs, i. e. preorder enumeration, breadth first enumeration, etc.  
 */
public class Main {

    public static void main(String[] args) {

        // create example list
        List<Node> nodes = createExampleList();

        // shuffle
        Collections.shuffle(nodes);

        logList("shuffled list", nodes);

        // convert list -> tree and tree -> sorted list
        DefaultMutableTreeNode root = createTree(nodes);
        List<Node> sortedList = createList(root);

        logList("sorted list", sortedList);

        System.exit(0);
    }

    private static DefaultMutableTreeNode createTree(List<Node> nodes) {

        // we want the final sublists sorted by name
        Collections.sort(nodes, new Comparator<Node>() {

            @Override
            public int compare(Node o1, Node o2) {
                return o1.text.compareTo(o2.text);
            }

        });

        // create DefaultMutableTreeNode objects for every node
        Map<Node, DefaultMutableTreeNode> treeNodeMap = new HashMap<>();
        for (Node node : nodes) {
            treeNodeMap.put(node, new DefaultMutableTreeNode(node));
        }

        DefaultMutableTreeNode root = null;

        // connect the tree nodes depending on their relation
        for (Node node : nodes) {

            DefaultMutableTreeNode treeNode = treeNodeMap.get(node);

            // find root node
            if (node.parent == null) {

                root = treeNode;

            }
            // otherwise attach the node to its parent
            else {

                // get the parent treenode
                DefaultMutableTreeNode parentTreeNode = treeNodeMap.get(node.parent);

                // attach the current node to its parent
                parentTreeNode.add(treeNode);

            }
        }

        return root;
    }

    private static List<Node> createList(DefaultMutableTreeNode root) {

        List<Node> nodes = new ArrayList<>();

        // iterate through the tree in preorder, extract the node object and add it to the list. in addition the level is set as meta information, used later for indenting during logging
        Enumeration<DefaultMutableTreeNode> enumeration = root.preorderEnumeration();
        while (enumeration.hasMoreElements()) {

            // get tree node
            DefaultMutableTreeNode treeNode = enumeration.nextElement();

            // get node from tree node
            Node node = (Node) treeNode.getUserObject();

            // update the level
            node.level = treeNode.getLevel();

            // add to list
            nodes.add(node);
        }

        return nodes;
    }

    /**
     * Log the node list
     * @param text
     * @param list
     */
    private static void logList(String text, Collection<Node> list) {

        System.out.println();
        System.out.println(text);
        System.out.println();

        for (Node item : list) {
            String paddedString = createString( item.level * 2, ' ');
            System.out.println( "  " + paddedString + item);
        }

    }

    /**
     * Create a string filled with {@code length} times the given {@code character}.
     * @param length
     * @param character
     * @return
     */
    public static String createString(int length, char character) {

        if (length <= 0)
            return "";

        char[] array = new char[length];

        Arrays.fill(array, character);

        return new String(array);
    }

    /**
     * Create example data
     * @return
     */
    private static List<Node> createExampleList() {

        List<Node> list = new ArrayList<>();

        Node root = new Node(null, "root");

        Node a = new Node(root, "a");
        Node b = new Node(root, "b");
        Node c = new Node(root, "c");

        Node a1 = new Node(a, "a1");
        Node a2 = new Node(a, "a2");
        Node a3 = new Node(a, "a3");

        Node b1 = new Node(b, "b1");
        Node b2 = new Node(b, "b2");
        Node b3 = new Node(b, "b3");

        Node c1 = new Node(c, "c1");
        Node c2 = new Node(c, "c2");
        Node c3 = new Node(c, "c3");


        Node b11 = new Node(b1, "b11");
        Node b12 = new Node(b1, "b12");
        Node b13 = new Node(b1, "b13");


        list.add(root);

        list.add(a);
        list.add(b);
        list.add(c);

        list.add(a1);
        list.add(a2);
        list.add(a3);

        list.add(b1);
        list.add(b11);
        list.add(b12);
        list.add(b13);

        list.add(b2);
        list.add(b3);

        list.add(c1);
        list.add(c2);
        list.add(c3);

        return list;
    }

    /**
     * Object with a parent relationship 
     */
    public static class Node {

        Node parent;
        String text;
        int level = -1;

        public Node(Node parent, String text) {
            this.parent = parent;
            this.text = text;
        }

        public String toString() {
            return text;
        }
    }

}

Output:

shuffled list

  b11
  a
  b13
  c2
  b1
  b3
  b
  c1
  a3
  c
  b12
  a1
  b2
  c3
  a2
  root

sorted list

  root
    a
      a1
      a2
      a3
    b
      b1
        b11
        b12
        b13
      b2
      b3
    c
      c1
      c2
      c3

Answer 1

One possibility is to use streams and recursion:

public static void main(String[] args) {
    // create example list
    List<Node> nodes = createExampleList();

    // shuffle
    Collections.shuffle(nodes);
    logList("shuffled list", nodes);

    // create tree list
    logList("tree list", treeList(nodes));
}

private static List<Node> treeList(final List<Node> nodes) {
    return treeAdd(nodes, null, new ArrayList<>(nodes.size()));
}

private static List<Node> treeAdd(List<Node> nodes, Node parent, List<Node> treeList) {
    nodes.stream()
            .filter(n -> n.parent == parent)
            .sorted((n1,n2) -> n1.text.compareTo(n2.text))
            .forEach(n -> {
        n.level = parent == null ? 0 : parent.level + 1;
        treeList.add(n);
        treeAdd(nodes, n, treeList);
    });
    return treeList;
}

Note that this is not super efficient in terms of performance since the filter invocation is called n times and is O(n). It could be optimised by pre-initialising a map to lookup children by parent.