- 追加された行はこの色です。
- 削除された行はこの色です。
TITLE:JTreeのソート
#navi(../)
#tags(JTree, TreeNode)
RIGHT:Posted by &author(aterai); at 2009-05-04
*JTreeのソート [#d8f8e60e]
``JTree``をソートします。[https://forums.oracle.com/forums/thread.jspa?threadID=1353435 OTN Discussion Forums : How to sort jTree Nodes]からの引用です。
---
category: swing
folder: SortTree
title: JTreeのソート
tags: [JTree, TreeNode, Comparator]
author: aterai
pubdate: 2009-05-04T16:26:55+09:00
description: JTreeを葉ノードより親ノード優先でノード名を比較するComparatorを使用してソートします。
image: https://lh6.googleusercontent.com/_9Z4BYR88imo/TQTThR240sI/AAAAAAAAAkg/h3mIbDu9xa4/s800/SortTree.png
hreflang:
href: https://java-swing-tips.blogspot.com/2013/09/how-to-sort-jtree-nodes.html
lang: en
---
* 概要 [#summary]
`JTree`を葉ノードより親ノード優先でノード名を比較する`Comparator`を使用してソートします。
-&jnlp;
-&jar;
-&zip;
#download(https://lh6.googleusercontent.com/_9Z4BYR88imo/TQTThR240sI/AAAAAAAAAkg/h3mIbDu9xa4/s800/SortTree.png)
//#screenshot
#ref(http://lh6.ggpht.com/_9Z4BYR88imo/TQTThR240sI/AAAAAAAAAkg/h3mIbDu9xa4/s800/SortTree.png)
**サンプルコード [#p11c3166]
* サンプルコード [#sourcecode]
#code(link){{
//Swing - How to sort jTree Nodes
//https://forums.oracle.com/forums/thread.jspa?threadID=1353435
public static DefaultMutableTreeNode sortTree(DefaultMutableTreeNode root) {
for(int i=0;i<root.getChildCount();i++) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode) root.getChildAt(i);
String nt = node.getUserObject().toString();
for(int j=0; j<i; j++) {
DefaultMutableTreeNode prevNode = (DefaultMutableTreeNode) root.getChildAt(j);
String np = prevNode.getUserObject().toString();
if(nt.compareToIgnoreCase(np)<0) {
root.insert(node, j);
root.insert(prevNode, i);
}
public static void sortTree(DefaultMutableTreeNode root) {
Enumeration e = root.depthFirstEnumeration();
while (e.hasMoreElements()) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode) e.nextElement();
if (!node.isLeaf()) {
sort2(node); // selection sort
// sort3(node); // JDK 1.6.0: iterative merge sort
// sort3(node); // JDK 1.7.0: TimSort
}
if(node.getChildCount() > 0) node = sortTree(node);
}
return root;
}
public static Comparator<DefaultMutableTreeNode> tnc = new Comparator<DefaultMutableTreeNode>() {
@Override public int compare(DefaultMutableTreeNode a, DefaultMutableTreeNode b) {
// ...
}
};
}}
**解説 [#n25f3e6d]
上記のサンプルでは、チェックボックスをクリックすると``JTree``を%%降順%% 昇順でソートするようになっています。
元のソート無しの状態に戻す場合は、``DefaultTreeModel``を作成し直しています。
**参考リンク [#g127d784]
- [https://forums.oracle.com/forums/thread.jspa?threadID=1353435 OTN Discussion Forums : How to sort jTree Nodes]
-- ``#6``のHamedさんの投稿
**コメント [#lff287f1]
- ソースにバグあります。 -- [[a]] &new{2013-07-02 (火) 15:53:41};
- root.insert(prevNode, i);の後にi--; を入れる必要あり -- [[a]] &new{2013-07-02 (火) 15:54:09};
-- ご指摘ありがとうございます。たしかに``i--;break``などがないと、入れ替えられてソートされないノードが出来てしまいますね。効率も悪いので、深さ優先で深いところにある親ノードから別の方法でソートするのもいいかもしれません。しばらくテストしてこのサンプルは修正したいと思います。 -- [[aterai]] &new{2013-07-03 (水) 13:11:51};
#code{{
//package example;
//-*- mode:java; encoding:utf-8 -*-
// vim:set fileencoding=utf-8:
//@homepage@
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import javax.swing.*;
import javax.swing.tree.*;
public class MainPanel extends JPanel {
private final DefaultMutableTreeNode root = makeTreeRoot();
private final JTree tree = new JTree(new DefaultTreeModel(makeTreeRoot()));
public MainPanel() {
super(new BorderLayout());
Box box = Box.createHorizontalBox();
box.add(new JCheckBox(new AbstractAction("0") {
@Override public void actionPerformed(ActionEvent e) {
JCheckBox check = (JCheckBox)e.getSource();
DefaultMutableTreeNode r = deepCopyTree(root, (DefaultMutableTreeNode)root.clone());
compare_count = 0;
swap_count = 0;
sortTree0(r);
System.out.format("compare: %d, swap: %d%n", compare_count, swap_count);
tree.setModel(new DefaultTreeModel(check.isSelected()?r:root));
expandAll(tree);
}
}));
box.add(new JCheckBox(new AbstractAction("1") {
@Override public void actionPerformed(ActionEvent e) {
JCheckBox check = (JCheckBox)e.getSource();
DefaultMutableTreeNode r = deepCopyTree(root, (DefaultMutableTreeNode)root.clone());
compare_count = 0;
swap_count = 0;
sortTree1(r);
System.out.format("compare: %d, swap: %d%n", compare_count, swap_count);
tree.setModel(new DefaultTreeModel(check.isSelected()?r:root));
expandAll(tree);
}
}));
box.add(new JCheckBox(new AbstractAction("2") {
@Override public void actionPerformed(ActionEvent e) {
JCheckBox check = (JCheckBox)e.getSource();
DefaultMutableTreeNode r = deepCopyTree(root, (DefaultMutableTreeNode)root.clone());
compare_count = 0;
swap_count = 0;
sortTree2(r);
System.out.format("compare: %d, swap: %d%n", compare_count, swap_count);
tree.setModel(new DefaultTreeModel(check.isSelected()?r:root));
expandAll(tree);
}
}));
box.add(new JCheckBox(new AbstractAction("3") {
@Override public void actionPerformed(ActionEvent e) {
JCheckBox check = (JCheckBox)e.getSource();
DefaultMutableTreeNode r = deepCopyTree(root, (DefaultMutableTreeNode)root.clone());
compare_count = 0;
swap_count = 0;
sortTree3(r);
System.out.format("compare: %d, swap: --%n", compare_count);
tree.setModel(new DefaultTreeModel(check.isSelected()?r:root));
expandAll(tree);
}
}));
box.add(new JCheckBox(new AbstractAction("4") {
@Override public void actionPerformed(ActionEvent e) {
JCheckBox check = (JCheckBox)e.getSource();
DefaultMutableTreeNode r = deepCopyTree(root, (DefaultMutableTreeNode)root.clone());
compare_count = 0;
swap_count = 0;
sortTree4(r);
System.out.format("compare: %d, swap: %d%n", compare_count, swap_count);
tree.setModel(new DefaultTreeModel(check.isSelected()?r:root));
expandAll(tree);
}
}));
add(box, BorderLayout.SOUTH);
add(makeTitledPanel("Sort JTree", tree));
expandAll(tree);
setPreferredSize(new Dimension(320, 200));
// selection sort
public static void sort2(DefaultMutableTreeNode parent) {
int n = parent.getChildCount();
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (tnc.compare((DefaultMutableTreeNode) parent.getChildAt(min),
(DefaultMutableTreeNode) parent.getChildAt(j)) > 0) {
min = j;
}
}
private static DefaultMutableTreeNode deepCopyTree(DefaultMutableTreeNode src, DefaultMutableTreeNode tgt) {
for(int i=0; i<src.getChildCount(); i++) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode)src.getChildAt(i);
DefaultMutableTreeNode clone = new DefaultMutableTreeNode(node.getUserObject());
//DefaultMutableTreeNode clone = (DefaultMutableTreeNode)node.clone();
tgt.add(clone);
if(!node.isLeaf()) {
deepCopyTree(node, clone);
}
}
return tgt;
if (i != min) {
MutableTreeNode a = (MutableTreeNode) parent.getChildAt(i);
MutableTreeNode b = (MutableTreeNode) parent.getChildAt(min);
parent.insert(b, i);
parent.insert(a, min);
}
}
}
}}
private JComponent makeTitledPanel(String title, JTree tree) {
JPanel p = new JPanel(new BorderLayout());
p.setBorder(BorderFactory.createTitledBorder(title));
p.add(new JScrollPane(tree));
return p;
}
#code{{
public static void sort3(DefaultMutableTreeNode parent) {
int n = parent.getChildCount();
// @SuppressWarnings("unchecked")
// Enumeration<DefaultMutableTreeNode> e = parent.children();
// ArrayList<DefaultMutableTreeNode> children = Collections.list(e);
List<DefaultMutableTreeNode> children = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
children.add((DefaultMutableTreeNode) parent.getChildAt(i));
}
Collections.sort(children, tnc); // using Arrays.sort(...)
parent.removeAllChildren();
for (MutableTreeNode node: children) {
parent.add(node);
}
}
}}
public static int compare_count = 0;
public static int swap_count = 0;
public static TreeNodeComparator tnc = new TreeNodeComparator();
* 解説 [#explanation]
上記のサンプルでは、チェックボックスがクリックされると以下の手順でソートを実行します。
//Swing - How to sort jTree Nodes
//https://forums.oracle.com/forums/thread.jspa?threadID=1353435
public static boolean DEBUG = true;
public static void sortTree0(DefaultMutableTreeNode root) {
for(int i=0;i<root.getChildCount();i++) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode) root.getChildAt(i);
for(int j=0; j<i; j++) {
DefaultMutableTreeNode prevNode = (DefaultMutableTreeNode) root.getChildAt(j);
compare_count++;
if(tnc.compare(node, prevNode)<0) {
root.insert(node, j);
root.insert(prevNode, i);
swap_count++;
if(DEBUG) {
i--;
break;
}
}
}
if(node.getChildCount() > 0) sortTree0(node);
}
}
- `DefaultTreeModel`から`deep copy`でクローンを作成
- クローンされたモデルのルート`DefaultMutableTreeNode`を深さ優先で探索することで昇順ソート
- ソート済みのモデルを`JTree`に設定
-- ソート無しの状態に戻す場合は、別途保存してある元の`DefaultTreeModel`を`JTree`に設定
public static void sortTree1(DefaultMutableTreeNode root) {
int n = root.getChildCount();
for(int i=0;i<n-1;i++) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode) root.getChildAt(i);
for(int j=i+1; j<n; j++) {
DefaultMutableTreeNode prevNode = (DefaultMutableTreeNode) root.getChildAt(j);
if(tnc.compare(node, prevNode)>0) {
swap_count++;
root.insert(node, j);
root.insert(prevNode, i);
i--;
break;
}
}
if(node.getChildCount() > 0) sortTree1(node);
}
}
----
- `DefaultMutableTreeNode`の比較は`Comparator<DefaultMutableTreeNode>#compare`をオーバーライドし、節ノードが葉ノードより上、かつ`getUserObject().toString()`で生成した文字列の大文字小文字を無視している
public static void sort2(DefaultMutableTreeNode parent) {
int n = parent.getChildCount();
for(int i=0; i<n-1; i++) {
int min = i;
for(int j=i+1; j<n; j++) {
if(tnc.compare(
(DefaultMutableTreeNode)parent.getChildAt(min),
(DefaultMutableTreeNode)parent.getChildAt(j))>0) {
min = j;
}
}
if(i!=min) {
swap_count++;
MutableTreeNode a = (MutableTreeNode)parent.getChildAt(i);
MutableTreeNode b = (MutableTreeNode)parent.getChildAt(min);
parent.insert(b, i);
parent.insert(a, min);
//MutableTreeNode node = (MutableTreeNode)parent.getChildAt(min);
//parent.insert(node, i);
//compare_count++;
}
}
#code{{
public static Comparator<DefaultMutableTreeNode> tnc = new Comparator<DefaultMutableTreeNode>() {
@Override public int compare(DefaultMutableTreeNode a, DefaultMutableTreeNode b) {
if (a.isLeaf() && !b.isLeaf()) {
return 1;
} else if (!a.isLeaf() && b.isLeaf()) {
return -1;
} else {
String sa = a.getUserObject().toString();
String sb = b.getUserObject().toString();
return sa.compareToIgnoreCase(sb);
}
public static void sortTree2(DefaultMutableTreeNode root) {
Enumeration e = root.depthFirstEnumeration();
while(e.hasMoreElements()) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode)e.nextElement();
if(!node.isLeaf()) {
sort2(node);
}
}
}
}
};
}}
public static void sort3(DefaultMutableTreeNode parent) {
int n = parent.getChildCount();
- `JDK 1.8.0`以降の場合、この`Comparator`を以下のように簡単に作成できる
-- 参考: [http://d.hatena.ne.jp/yohhoy/20141007/p1 Comparator with ラムダ式 - yohhoyの日記]
-- 参考: [https://docs.oracle.com/javase/jp/8/docs/api/java/util/Comparator.html#thenComparing-java.util.Comparator- Comparator#thenComparing(...) (Java Platform SE 8)]
@SuppressWarnings("unchecked")
Enumeration<DefaultMutableTreeNode> e = parent.children();
ArrayList<DefaultMutableTreeNode> children = Collections.list(e);
#code{{
Comparator<String> sci = Comparator.comparingInt(String::length)
.thenComparing(String.CASE_INSENSITIVE_ORDER);
Comparator<DefaultMutableTreeNode> tnc = Comparator.comparing(DefaultMutableTreeNode::isLeaf)
.thenComparing(n -> n.getUserObject().toString(), sci);
// .thenComparing(n -> n.getUserObject().toString().toLowerCase());
}}
//java.util.List<DefaultMutableTreeNode> children = new ArrayList<DefaultMutableTreeNode>(n);
//for(int i=0; i<n; i++) {
// children.add((DefaultMutableTreeNode)parent.getChildAt(i));
//}
Collections.sort(children, tnc);
parent.removeAllChildren();
for(MutableTreeNode node: children) {
parent.add(node);
}
}
public static void sortTree3(DefaultMutableTreeNode root) {
Enumeration e = root.depthFirstEnumeration();
while(e.hasMoreElements()) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode)e.nextElement();
if(!node.isLeaf()) {
sort3(node);
}
}
}
----
- `sort3`で使用している`Collections.sort(...)`は内部で`Arrays.sort(T[], Comparator<? super T>)`を使用しているので、`JDK 1.6.0`と`JDK 1.7.0`以降でソートアルゴリズムが異なる
-- 参考: [https://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort Is Java 7 using Tim Sort for the Method Arrays.Sort? - Stack Overflow]
public static void sortTree4(DefaultMutableTreeNode root) {
Enumeration e = root.children();
while(e.hasMoreElements()) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode)e.nextElement();
if(!node.isLeaf()) {
sortTree4(node);
}
}
sort2(root);
}
- `JDK 1.6.0`
#code{{
// Arrays.sort(T[] a, Comparator<? super T> c)
public static <T> void sort(T[] a, Comparator<? super T> c) {
T[] aux = (T[]) a.clone();
if (c == null) {
mergeSort(aux, a, 0, a.length, 0);
} else {
mergeSort(aux, a, 0, a.length, 0, c);
}
}
}}
static class TreeNodeComparator implements Comparator<DefaultMutableTreeNode>{
@Override public int compare(DefaultMutableTreeNode a, DefaultMutableTreeNode b) {
compare_count++;
if(a.isLeaf() && !b.isLeaf()) {
return 1;
}else if(!a.isLeaf() && b.isLeaf()) {
return -1;
}else{
String sa = a.getUserObject().toString();
String sb = b.getUserObject().toString();
return sa.compareToIgnoreCase(sb);
}
}
- `JDK 1.7.0`
#code{{
// Arrays.sort(T[] a, Comparator<? super T> c)
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested) {
legacyMergeSort(a, c);
} else {
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
private static DefaultMutableTreeNode makeTreeRoot() {
DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");
DefaultMutableTreeNode set1 = new DefaultMutableTreeNode("Set 001");
DefaultMutableTreeNode set2 = new DefaultMutableTreeNode("Set 002");
DefaultMutableTreeNode set3 = new DefaultMutableTreeNode("Set 003");
DefaultMutableTreeNode set4 = new DefaultMutableTreeNode("Set 004");
set1.add(new DefaultMutableTreeNode("3333333333333333"));
set1.add(new DefaultMutableTreeNode("111111111"));
set1.add(new DefaultMutableTreeNode("22222222222"));
set1.add(set4);
set1.add(new DefaultMutableTreeNode("22222222222"));
set1.add(new DefaultMutableTreeNode("22222222222"));
set2.add(new DefaultMutableTreeNode("eeeeeeeeeeeee"));
set2.add(new DefaultMutableTreeNode("bbbbbbbbbbbb"));
set3.add(new DefaultMutableTreeNode("zzzzzzz"));
set3.add(new DefaultMutableTreeNode("aaaaaaaaaaaa"));
set3.add(new DefaultMutableTreeNode("ccccccccc"));
set4.add(new DefaultMutableTreeNode("22222222222"));
set4.add(new DefaultMutableTreeNode("eeeeeeeeeeeee"));
set4.add(new DefaultMutableTreeNode("bbbbbbbbbbbb"));
set4.add(new DefaultMutableTreeNode("zzzzzzz"));
root.add(new DefaultMutableTreeNode("xxxxxxxxxxxxx"));
root.add(set3);
root.add(new DefaultMutableTreeNode("eeeeeeeeeeeee"));
root.add(set1);
root.add(set2);
root.add(new DefaultMutableTreeNode("22222222222"));
root.add(new DefaultMutableTreeNode("bbbbbbbbbbbb"));
return root;
}
private void expandAll(JTree tree) {
int row = 0;
while(row<tree.getRowCount()) {
tree.expandRow(row);
row++;
}
}
public static void main(String[] args) {
EventQueue.invokeLater(new Runnable() {
@Override public void run() {
createAndShowGUI();
}
});
}
public static void createAndShowGUI() {
try{
UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
}catch(Exception e) {
e.printStackTrace();
}
JFrame frame = new JFrame("@title@");
frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
frame.getContentPane().add(new MainPanel());
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
}
}
}
}}
* 参考リンク [#reference]
- [https://community.oracle.com/thread/1355435 Swing - How to sort jTree Nodes]
-- 以下のコメントにバグの指摘あり
//-- `#6`のHamedさんの投稿 (以下のコメントにバグの指摘あり)
- [[JTreeのノードを走査する>Swing/TraverseAllNodes]]
-- `JTree`ノードの深さ優先探索などについて
- [[JComboBoxのモデルとしてenumを使用する>Swing/SortingAnimations]]
-- 各種ソートアルゴリズムのサンプル
- [[JTableでファイルとディレクトリを別々にソート>Swing/FileDirectoryComparator]]
-- ディレクトリが先になる比較について
* コメント [#comment]
#comment
- ソースにバグあります。 `root.insert(prevNode, i);`の後に`i--;`を入れる必要あり -- &user(a); &new{2013-07-02 (火) 15:54:09};
-- ご指摘ありがとうございます。たしかに`i--;break`などがないと、入れ替えられてソートされないノードが出来てしまいますね。効率も悪いので、深さ優先で探索した親ノードから別の方法でソートするように変更した方がいいかもしれません。 %%しばらくテストしてこのサンプルは修正したいと思います。%% 修正しました。 -- &user(aterai); &new{2013-07-03 (水) 13:11:51};
#comment