Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.gui > #3135 > unrolled thread

Re: Sortable Java Tree Ta

Back to article view | Back to comp.lang.java.gui

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Sortable Java Tree Ta arvim85@gmail.com.remove-dii-this - 2011-04-27 15:43 +0000
    Re: Sortable Java Tree Ta "Roedy Green" <roedy.green@THRWHITE.remove-dii-this> - 2011-04-27 15:43 +0000
    Re: Sortable Java Tree Ta "Rogan Dawes" <rogan.dawes@THRWHITE.remove-dii-this> - 2011-04-27 15:43 +0000
      Re: Sortable Java Tree Ta "Roedy Green" <roedy.green@THRWHITE.remove-dii-this> - 2011-04-27 15:43 +0000
        Re: Sortable Java Tree Ta "Roedy Green" <roedy.green@THRWHITE.remove-dii-this> - 2011-04-27 15:43 +0000
          Re: Sortable Java Tree Ta "Rogan Dawes" <rogan.dawes@THRWHITE.remove-dii-this> - 2011-04-27 15:43 +0000
        Re: Sortable Java Tree Ta "Rogan Dawes" <rogan.dawes@THRWHITE.remove-dii-this> - 2011-04-27 15:43 +0000

#3135 — Re: Sortable Java Tree Ta

  To: comp.lang.java.gui
anyOne give detailed idea of doing sorting for JTreeTable.....??
i cant understand the already posted things....need of some
detailed .......

---
 * Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [next] | [standalone]

#3138

  To: comp.lang.java.gui
On Mon, 11 Feb 2008 02:04:05 -0800 (PST), "arvim85@gmail.com"
<arvim85@gmail.com> wrote, quoted or indirectly quoted someone who
said :

>anyOne give detailed idea of doing sorting for JTreeTable.....??

There is an example posted at http://mindprod.com/jgloss/jtable.html

Look at the VerCheck example.  It sorts the model when you press a
button, and fires the change event to repaint the screen.  

What gets tricky is putting gismos on the header to get the user
decide which columns to sort and whether ascending/descending.

I did it in one commercial app where there was a arrow the pointed in
the direction of the current sort.  If you clicked it sorted in the
opposite direction.  It also maintained the table is that order when
the user entered data or the server sent new data.  That was more
complicated since I had to figure out the insertion point.

--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

---
 * Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [prev] | [next] | [standalone]

#3139

  To: comp.lang.java.gui
arvim85@gmail.com wrote:
> anyOne give detailed idea of doing sorting for JTreeTable.....??
> i cant understand the already posted things....need of some
> detailed .......

What can't you understand?

The big thing that I was trying to point out in this thread, and which 
Roedy seems to be missing repeatedly, is that sorting a *TREE* is very 
different from sorting a *TABLE*.

Yes, a JTreeTable looks like a JTable (and in fact is implemented using 
an adapter from a JTree to a JTable), but the underlying order is 
determined by the *TREE*. Note that the TreeTableModel extends 
TreeModel, not TableModel!

Once you define how you want to sort your *TREE*, we can help you with 
an implementation. So, give us some information about what is being 
represented in your tree.

Is it a filesystem? If so, sorting the *TREE* could be done by sorting 
the individual files within their directories. e.g. to Sort by file 
size. Of course, it makes no sense to sort the *directories* by size, 
since the intrinsic size of a directory is pretty meaningless unless you 
define it to be the aggregate of the sizes of the files and directories, 
for example. In *that* case, you could sort the tree nodes 
hierarchically so that the directories with the biggest contents show up 
first in the tree.

My ultimate point being: Without defining how you want to sort the tree, 
we can't help you with an implementation.

Rogan
(who is tired of this thread, and will give up on it unless someone 
actually posts useful information)

---
 * Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [prev] | [next] | [standalone]

#3140

  To: comp.lang.java.gui
On Tue, 12 Feb 2008 14:40:57 +0200, Rogan Dawes <discard@dawes.za.net>
wrote, quoted or indirectly quoted someone who said :

>The big thing that I was trying to point out in this thread, and which 
>Roedy seems to be missing repeatedly, is that sorting a *TREE* is very 
>different from sorting a *TABLE*.

Sorry, I always muddle those two.  Sorting a tree is not a common
operation.  I just read it as sort a table.

I presume you mean just sort the children of each node. It looks as
though you must sort, and if the order has changed, remove all elts
past the point of change, and re-add them in the new order.


--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

---
 * Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [prev] | [next] | [standalone]

#3145

  To: comp.lang.java.gui
On Tue, 12 Feb 2008 18:02:43 GMT, Roedy Green
<see_website@mindprod.com.invalid> wrote, quoted or indirectly quoted
someone who said :

>I presume you mean just sort the children of each node. It looks as
>though you must sort, and if the order has changed, remove all elts
>past the point of change, and re-add them in the new order.

I explain this in more detail at
http://mindprod.com/jgloss/jtree.html#SORTING
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

---
 * Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [prev] | [next] | [standalone]

#3155

  To: comp.lang.java.gui
Roedy Green wrote:
> On Tue, 12 Feb 2008 18:02:43 GMT, Roedy Green
> <see_website@mindprod.com.invalid> wrote, quoted or indirectly quoted
> someone who said :
> 
>> I presume you mean just sort the children of each node. It looks as
>> though you must sort, and if the order has changed, remove all elts
>> past the point of change, and re-add them in the new order.
> 
> I explain this in more detail at
> http://mindprod.com/jgloss/jtree.html#SORTING

I took a look at your approach, and have a couple of comments:

> Sorting
> I have never actually done this, but if I wanted to sort a JTree,
> here  is how I would go about it:
> 
>    1. Do a breadth first traversal of the the tree.
Duplicated "the". :-)

>    2. At each node extract a list of the childen into an array.
>    3. Sort the array.
>    4. If all is well, that part of the tree is already in order. 
>       If not, delete the children, leaving the early ones (if any)
>       which are already in order, then re-add the out of order ones 
>       in sorted order. Don't fire any change events yet.
>    5. When you have sorted the entire tree, fire a tree structure 
>       change event on the root.

Firing a TreeStructureChanged event at the root will tell JTree to 
collapse the tree, losing any expanded state. This is unlikely to be 
desirable. Unfortunately, the only good solution is store the selection 
and expansion state before the sort is executed, and restore it afterwards.

Here is a complete implementation of a Sortable TreeModel. It includes 
sample code to demonstrate its usage, including saving and restoring the 
selection and expansion states, as well as handling mutation events 
fired by the underlying TreeModel.

Enjoy.

Rogan Dawes

package sort;

/**
  * This code is released into the public domain
  */

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

import javax.swing.event.TreeModelEvent;
import javax.swing.event.TreeModelListener;
import javax.swing.tree.TreeModel;
import javax.swing.tree.TreePath;

/**
  * @author Rogan Dawes <SortedTreeModel @ dawes.za.net>
  *
  */
public class SortedTreeModel extends AbstractTreeModel {

     private TreeModel delegate;

     private Comparator<Object> comparator = null;

     private Map<Object, int[]> viewToModel = new HashMap<Object, int[]>();

     private Listener listener = new Listener();

     /**
      * Constructs a sorted TreeModel, based on the data in the provided 
delegate,
      * sorted according to the initial Comparator provided
      * @param delegate the underlying TreeModel to wrap
      * @param comparator the initial Comparator to use when sorting the 
nodes
      */
     public SortedTreeModel(TreeModel delegate, Comparator<Object> 
comparator) {
         this.delegate = delegate;
         setComparator(comparator);
         delegate.addTreeModelListener(listener);
     }

     public Object getChild(Object parent, int index) {
         int[] viewToModel = getViewToModel(parent);
         if (viewToModel == null)
             return delegate.getChild(parent, index);
         return delegate.getChild(parent, viewToModel[index]);
     }

     public int getChildCount(Object parent) {
         return delegate.getChildCount(parent);
     }

     public int getIndexOfChild(Object parent, Object child) {
         int index = delegate.getIndexOfChild(parent, child);
         int[] viewToModel = getViewToModel(parent);
         if (viewToModel == null)
             return index;
         for (int i = 0; i < viewToModel.length; i++)
             if (viewToModel[i] == index)
                 return i;
         throw new RuntimeException("This should never happen");
     }

     public Object getRoot() {
         return delegate.getRoot();
     }

     public boolean isLeaf(Object node) {
         return delegate.isLeaf(node);
     }

     public void valueForPathChanged(TreePath path, Object newValue) {
         delegate.valueForPathChanged(path, newValue);
     }

     /**
      * Set the new Comparator to use to sort the underlying tree nodes
      * @param comparator the comparator
      */
     public void setComparator(Comparator<Object> comparator) {
         this.comparator = comparator;
         if (sort(new TreePath(getRoot()), true))
             fireStructureChanged();
     }

     /**
      * Sorts the children of the node at the specified path, and 
optionally all of its
      * children
      * @param path the path to the node to sort
      * @param recursive whether to sort that node's children as well
      * @return true if any changes were made to the order of the nodes, 
false otherwise
      */
     protected boolean sort(TreePath path, boolean recursive) {
         Object parent = path.getLastPathComponent();
         int childCount = delegate.getChildCount(parent);
         if (childCount == 0)
             return false;
         Object[] children = new Object[childCount];
         int[] viewToModel = new int[childCount];
         for (int i = 0; i < childCount; i++) {
             children[i] = delegate.getChild(parent, i);
         }
         Arrays.sort(children, comparator);
         for (int i = 0; i < childCount; i++)
             viewToModel[i] = delegate.getIndexOfChild(parent, children[i]);
         boolean changed = setViewToModel(parent, viewToModel);
         if (recursive)
             for (int i=0; i<childCount; i++)
                 changed |= sort(path.pathByAddingChild(children[i]), 
recursive);
         return changed;
     }

     private int[] getViewToModel(Object parent) {
         return viewToModel.get(parent);
     }

     /**
      * Store the array mapping entries from the underlying model to the 
sorted order
      * As an optimization, if the sort order is identical to the 
underlying data order, we
      * do not store a mapping
      * @param parent the node whose children are represented
      * @param mapping the mapping from view order to underlying model order
      * @return true if the mapping differs from the current mapping, 
false otherwise
      */
     private boolean setViewToModel(Object parent, int[] mapping) {
         boolean identity = true;
         for (int i=0; i<mapping.length; i++)
             if (mapping[i] != i) {
                 identity = false;
                 break;
             }
         if (identity)
             mapping = null;
         int[] oldMapping = getViewToModel(parent);
         if (!equals(oldMapping, mapping)) {
             if (mapping == null) {
                 viewToModel.remove(parent);
             } else {
                 viewToModel.put(parent, mapping);
             }
             return true;
         }
         return false;
     }

     /**
      * Compare two integer arrays for equality
      * @param a an array
      * @param b an array
      * @return true if both arrays are null, or contain the same values 
in order
      */
     private boolean equals(int[] a, int[] b) {
         if (a == b) return true;
         if (a == null || b == null) return false;
         if (a.length != b.length) return false;
         for (int i=0; i<a.length; i++)
             if (a[i] != b[i])
                 return false;
         return true;
     }

     private class Listener implements TreeModelListener {

         /**
          * remaps the indices provided in the event to those in the 
sorted model
          * @param path the path of the parent node
          * @param indices the unsorted indices
          */
         private int[] remapIndices(TreePath path, int[] indices) {
             int[] mapping = getViewToModel(path.getLastPathComponent());
             if (mapping == null)
                 return indices;

             int[] newIndices = new int[indices.length];
             for (int i=0; i<indices.length; i++) {
                 for (int j=0; j<mapping.length; j++) {
                     if (mapping[j] == indices[i]) {
                         newIndices[i] = j;
                         break;
                     }
                 }
             }
             return newIndices;
         }

         /* (non-Javadoc)
          * @see 
javax.swing.event.TreeModelListener#treeNodesChanged(javax.swing.event.TreeModelEvent)
          */
         public void treeNodesChanged(TreeModelEvent e) {
             int[] indices = e.getChildIndices();
             TreePath path = e.getTreePath();
             indices = remapIndices(path, indices);
             fireChildrenChanged(path, indices, e.getChildren());
         }

         /* (non-Javadoc)
          * @see 
javax.swing.event.TreeModelListener#treeNodesInserted(javax.swing.event.TreeModelEvent)
          */
         public void treeNodesInserted(TreeModelEvent e) {
             int[] indices = e.getChildIndices();
             TreePath path = e.getTreePath();
             sort(e.getTreePath(), false);
             indices = remapIndices(path, indices);
             fireChildrenAdded(path, indices, e.getChildren());
         }

         /* (non-Javadoc)
          * @see 
javax.swing.event.TreeModelListener#treeNodesRemoved(javax.swing.event.TreeModelEvent)
          */
         public void treeNodesRemoved(TreeModelEvent e) {
             int[] indices = e.getChildIndices();
             TreePath path = e.getTreePath();
             indices = remapIndices(path, indices);
             sort(e.getTreePath(), false);
             fireChildrenRemoved(path, indices, e.getChildren());
         }

         /* (non-Javadoc)
          * @see 
javax.swing.event.TreeModelListener#treeStructureChanged(javax.swing.event.TreeModelEvent)
          */
         public void treeStructureChanged(TreeModelEvent e) {
             fireTreeStructureChanged(e.getTreePath());
         }

     }

     public static void main(String[] args) {
         final javax.swing.tree.DefaultMutableTreeNode root = new 
javax.swing.tree.DefaultMutableTreeNode("node");
         buildTree(root, 5, 3);
         final javax.swing.tree.DefaultTreeModel delegate = new 
javax.swing.tree.DefaultTreeModel(root);
         final SortedTreeModel sorted = new SortedTreeModel(delegate, 
new StringNodeComparator(1, true));
         final javax.swing.JTree tree = new javax.swing.JTree(sorted);
         javax.swing.JFrame frame = new javax.swing.JFrame("SortableTree");
         javax.swing.JScrollPane scrollPane = new 
javax.swing.JScrollPane(tree);
         javax.swing.JButton sort = new javax.swing.JButton("Sort");
         final StringNodeComparator[] comparators = new 
StringNodeComparator[] {
                 new StringNodeComparator(-1, false),
                 new StringNodeComparator(1, false),
                 new StringNodeComparator(-1, true),
                 new StringNodeComparator(1, true),
         };
         sort.addActionListener(new java.awt.event.ActionListener() {
             private int i = 0;
             private java.util.List<TreePath> expansion = new 
java.util.ArrayList<TreePath>();
             private TreePath[] selection;

             public void actionPerformed(java.awt.event.ActionEvent ae) {
                 saveSelectionAndExpansion();

                 System.out.println(comparators[i]);
                 sorted.setComparator(comparators[i]);
                 i = (i + 1) % comparators.length;

                 restoreSelectionAndExpansion();
             }

             private void saveSelectionAndExpansion() {
                 expansion.clear();
                 java.util.Enumeration<TreePath> e = 
tree.getExpandedDescendants(new TreePath(sorted.getRoot()));
                 while (e.hasMoreElements())
                     expansion.add(e.nextElement());
                 selection = tree.getSelectionPaths();
             }

             private void restoreSelectionAndExpansion() {
                 tree.setSelectionPaths(selection);
                 java.util.Iterator<TreePath> it = expansion.iterator();
                 while (it.hasNext())
                     tree.expandPath(it.next());
             }
         });
         javax.swing.JButton mutate = new javax.swing.JButton("Mutate");
         mutate.addActionListener(new java.awt.event.ActionListener() {
             private boolean running = false;
             private Thread mutator = new Thread(new Runnable() {
                 public void run() {
                     try {
                       java.util.Random random = new java.util.Random();
                       while (running) {
                           int i = Math.abs(random.nextInt()) % 
delegate.getChildCount(root);
                           final javax.swing.tree.MutableTreeNode child 
= (javax.swing.tree.MutableTreeNode) delegate.getChild(root, i);
                           java.awt.EventQueue.invokeLater(new Runnable() {
                               public void run() {
                                   delegate.removeNodeFromParent(child); 

                               }
                           });
                           Thread.sleep(1000);
                           java.awt.EventQueue.invokeLater(new Runnable() {
                               public void run() {
                                   delegate.insertNodeInto(child, root, 0);
                               }
                           });
                           Thread.sleep(1000);
                       }
                   } catch (InterruptedException ie) {
                   }
                 }
             });
             public void actionPerformed(java.awt.event.ActionEvent ae) {
                 if (!running) {
                     running = true;
                     mutator.start();
                 } else {
                     running = false;
                 }
             }
         });
         frame.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
         frame.getContentPane().setLayout(new java.awt.BorderLayout());
         frame.getContentPane().add(scrollPane, 
java.awt.BorderLayout.CENTER);
         frame.getContentPane().add(sort, java.awt.BorderLayout.NORTH);
         frame.getContentPane().add(mutate, java.awt.BorderLayout.SOUTH);
         frame.setBounds(200, 200, 400, 400);
         frame.setVisible(true);
     }

     private static void buildTree(javax.swing.tree.MutableTreeNode 
parent, int breadth, int depth) {
         if (depth == 0)
             return;
         for (int i=0; i<breadth; i++) {
             javax.swing.tree.MutableTreeNode node = new 
javax.swing.tree.DefaultMutableTreeNode(parent + "-" + i);
             parent.insert(node, i);
             buildTree(node, breadth, depth - 1);
         }
     }

     private static class StringNodeComparator implements 
Comparator<Object> {

         private int order;
         private boolean leavesOnly;

         public StringNodeComparator(int order, boolean leavesOnly) {
             this.order = order;
             this.leavesOnly = leavesOnly;
         }
         /* (non-Javadoc)
          * @see java.util.Comparator#compare(java.lang.Object, 
java.lang.Object)
          */
         public int compare(Object o1, Object o2) {
             javax.swing.tree.TreeNode t1 = (javax.swing.tree.TreeNode) o1;
             javax.swing.tree.TreeNode t2 = (javax.swing.tree.TreeNode) o2;
             int c = o1.toString().compareTo(o2.toString());
             if (leavesOnly)
                 if (t1.isLeaf() && t2.isLeaf()) {
                     return order * c;
                 } else
                     return c;
             return order * c;
         }

         public String toString() {
             return "Sorting " + (leavesOnly ? "leaves only " : "") + 
"in " + (order == -1 ? "reverse " : "") + "alphabetical order";
         }
     }
}

---
 * Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [prev] | [next] | [standalone]

#3146

  To: comp.lang.java.gui
Roedy Green wrote:
> On Tue, 12 Feb 2008 14:40:57 +0200, Rogan Dawes <discard@dawes.za.net>
> wrote, quoted or indirectly quoted someone who said :
> 
>> The big thing that I was trying to point out in this thread, and which 
>> Roedy seems to be missing repeatedly, is that sorting a *TREE* is very 
>> different from sorting a *TABLE*.
> 
> Sorry, I always muddle those two.  Sorting a tree is not a common
> operation.  I just read it as sort a table.
> 
> I presume you mean just sort the children of each node. It looks as
> though you must sort, and if the order has changed, remove all elts
> past the point of change, and re-add them in the new order.

Well, I guess you could write a SortedTreeModel adapter class that 
contains a similar node pattern to the underlying TreeModel, along with 
int[] arrays mapping viewToModel and modelToView

e.g.

public class SortedTreeModel extends AbstractTreeModel {

private Map<Object, int[]> viewToModel;
private Comparator comparator;

public SortedTreeModel(TreeModel delegate) {
     viewToModel = new HashMap<Object, int[]>();
     this.delegate = delegate;
}

public Object getChild(Object parent, int index) {
     int[] viewToModel = getViewToModel(parent);
     if (viewToModel == null)
         return delegate.getChild(parent, index);
     return delegate.getChild(parent, viewToModel[index]);
}

public int getChildCount(Object parent) {
     return delegate.getChildCound(parent);
}

public int getIndexOfChild(Object parent, Object child) {
     int index = delegate.getIndexOfChild(parent, child);
     int[] viewToModel = getViewToModel(parent);
     if (viewToModel == null)
         return index;
     for (int i=0; i<viewToModel.length; i++)
         if (viewToModel[i] == index)
             return i;
     throw new RuntimeException("This should never happen");
}

public Object getRoot() {
     return delegate.getRoot();
}

public boolean isLeaf(Object node) {
     return delegate.isLeaf(node);
}

public void valueForPathChanged(TreePath path, Object newValue) {
     delegate.valueForPathChanged(path, newValue);
}

protected int[] getViewToModel(Object parent) {
     return viewToModel.get(parent);
}

public void setComparator(Comparator comparator) {
     this.comparator = comparator;
     sort(new TreePath(getRoot()), true);
}

protected void sort(TreePath path, boolean recursive) {
     Object parent = path.lastPathComponent();
     int childCount = delegate.getChildCount(parent);
     if (childCount == 0)
         return;
     Object[] children = new Object[childCount];
     int[] viewToModel = new int[childCount];
     for (int i=0; i<childCount; i++) {
         children[i] = delegate.getChild(parent, i);
         if (recursive)
             sort(path.pathByAddingChild(children[i]), recursive);
     }
     Arrays.sort(children, comparator);
     for (int i=0; i<childCount; i++)
         viewToModel[i] = delegate.getIndexOfChild(parent, children[i]);
     this.viewToModel.put(parent, viewToModel);
     fireChildrenChanged(path, childrenArray[children.length], children);
}

private int[] childrenArray(int size) {
     int[] a = new int[size];
     for (int i=0; i<size; i++)
         a[i] = i;
     return a;
}

}

This *should* work, but since I wrote it in my news reader, I make no 
guarantees it will even compile.

Now, all you need to do is implement a Comparator for your nodes. And if 
it is a dynamic TreeModel, then you need to add the necessary listener 
to the delegate and call sort(node) (or sort(node, true) ) whenever the 
node changes.

Use it like so:

TreeModel delegate = . . . ; // your underlying TreeModel
TreeModel sorted = new SortedTreeModel(delegate);
JTree tree = new JTree(sorted);
Comparator comp = new MyComparator();
sorted.setComparator(comp);

Obviously, you can extend the identical technique to TreeTableModel.

NOTE: You can try to be more fine grained in your event firing, of course.

Rogan

---
 * Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.gui

csiph-web