ソート私はデータオブジェクトとの順不同リストを持っている木

Question

状況

のような親参照してリストは、各オブジェクトは、その親への参照を持っています。リストはparentへの参照によってソートされるべきであり、最終リストはツリーのように順番に並ぶべきである。子供は名前で注文する必要があります。

データオブジェクト：

/** 
* 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; 
    } 
} 

例ツリー：

/** 
* 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; 
} 

問題

私の現在のソリューションは、メモリ上に重いです。私がこれまで持っているアルゴリズム：

• は、すべてのオブジェクトのDefaultMutableTreeNodeを作成し、すべてのオブジェクトを通じてマップ
• 反復に入れて、オブジェクトの親のDefaultMutableTreeNode表現を取得し、親
にノードを追加します
• 反復

質問

ツリーをトラバースし、リストに各項目を追加する DefaultMutableTreeNodeの列挙メカニズムを使用

もっと速く、より効率的な方法を知っている人はいますか？

コード

は、ここで私がこれまで持っているコードです：

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

} 

が出力：

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

一つの可能​​性はストリームと再帰を使用することです：

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

これは、フィルタ呼び出しがn回呼び出され、O（n）であるため、パフォーマンス面で効率的ではないことに注意してください。親によって子を参照するようにマップを事前に初期化することによって最適化することができます。