Skip to main content

Tree filtering

7 replies [Last post]
aephyr
Offline
Joined: 2009-11-20

There doesn't seem to be any decent tree filtering on offer anywhere does there?

When I searched, about all I found was this discouraging note: PENDING: support filtering/sorting - that was in the javadoc for JXTree over in the labs.

I had previously just implemented the filtering directly in the TreeModel. However, this became a problem when I decided/needed to share the node structure between two components. The first, a regular JTree; the second, a breadcrumb bar which I called TreeMenuBar because 1) it extends JMenuBar, 2) it uses a JTree component in the JPopupMenu for the JMenus on the JMenuBar. The filtering applied to the first component shouldn't show up in the second component.

So I have created a model wrapper that does the actual filtering and leaves the original node structure alone. Here is the prototype, hardly a finished piece of work - just all I am willing to put into it for today. As for why I put Sort in the main class name when it does not do any actual sorting - who knows? Comments/Suggestions please :)

[code]

import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.util.regex.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.tree.*;

public class TreeSort2 implements Runnable, ActionListener {
public static void main(String[] args) throws Exception {
SwingUtilities.invokeLater(new TreeSort2());
}

@Override
public void run() {
tree = new JTree();
tree.setModel(new Model(tree.getModel()));
JPanel north = new JPanel();
filter = new JTextField(15);
filter.addActionListener(this);
north.add(filter);
JFrame frame = new JFrame(getClass().getSimpleName());
frame.add(north, BorderLayout.NORTH);
frame.add(new JScrollPane(tree), BorderLayout.CENTER);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
}

private JTextField filter;
private JTree tree;

@Override
public void actionPerformed(ActionEvent e) {
if (e.getSource() == filter) {
Model model = (Model)tree.getModel();
String regex = filter.getText();

ArrayList expand = model.setFilter(
regex.isEmpty() ? null : new RegexFilter(regex, false));
if (expand != null)
for (TreePath path : expand)
tree.expandPath(path);

}
}

private interface Filter {
boolean acceptNode(TreePath parent, Object node, boolean leaf);
}

private static class RegexFilter implements Filter {
RegexFilter(String regex, boolean leaf) {
matcher = Pattern.compile(regex).matcher("");
leafOnly = leaf;
}

private Matcher matcher;

private boolean leafOnly;

public boolean acceptNode(TreePath parent, Object node, boolean leaf) {
if (leafOnly && !leaf)
return false;
matcher.reset(node.toString());
return matcher.find();
}
}

private static class Converter {

Converter(int[] vtm) {
viewToModel = vtm;
}

private int[] viewToModel;

int getChildCount() {
return viewToModel.length;
}

int convertRowIndexToView(int index) {
int[] vtm = viewToModel;
for (int i=vtm.length; --i>=0;) {
if (vtm[i] == index)
return i;
}
return -1;
}

int convertRowIndexToModel(int index) {
return viewToModel

;
}
}

private static class Model implements TreeModel {
Model(TreeModel model) {
this.model = model;
}

private TreeModel model;

private Map map;

protected EventListenerList listenerList = new EventListenerList();

@Override
public void addTreeModelListener(TreeModelListener l) {
listenerList.add(TreeModelListener.class, l);
}

@Override
public void removeTreeModelListener(TreeModelListener l) {
listenerList.remove(TreeModelListener.class, l);
}

private Converter getConverter(Object node) {
return map == null ? null : map.get(node);
}

int convertRowIndexToView(Object parent, int index) {
Converter converter = getConverter(parent);
if (converter != null)
return converter.convertRowIndexToView(index);
return index;
}

int convertRowIndexToModel(Object parent, int index) {
Converter converter = getConverter(parent);
if (converter != null)
return converter.convertRowIndexToModel(index);
return index;
}

@Override
public Object getChild(Object parent, int index) {
return model.getChild(parent, convertRowIndexToModel(parent, index));
}

@Override
public int getChildCount(Object parent) {
Converter converter = getConverter(parent);
if (converter != null)
return converter.getChildCount();
return model.getChildCount(parent);
}

@Override
public int getIndexOfChild(Object parent, Object child) {
int index = model.getIndexOfChild(parent, child);
if (index < 0)
return -1;
return convertRowIndexToView(parent, index);
}

@Override
public Object getRoot() {
return model.getRoot();
}

@Override
public boolean isLeaf(Object node) {
Converter converter = getConverter(node);
if (converter != null)
return false;
return model.isLeaf(node);
}

@Override
public void valueForPathChanged(TreePath path, Object newValue) {
model.valueForPathChanged(path, newValue);
}

ArrayList setFilter(Filter filter) {
ArrayList expand = null;
if (filter == null) {
map = null;
} else {
map = new HashMap();
expand = new ArrayList();
if (!applyFilter(filter, null, model.getRoot(), expand)) {
map.put(model.getRoot(), new Converter(new int[0]));
}
}
fireTreeStructureChanged();
return expand;
}

private void fireTreeStructureChanged() {
Object[] listeners = listenerList.getListenerList();
TreeModelEvent e = null;
for (int i = listeners.length-2; i>=0; i-=2) {
if (listeners[i]==TreeModelListener.class) {
if (e == null)
e = new TreeModelEvent(this, new TreePath(getRoot()), null, null);
((TreeModelListener)listeners[i+1]).treeStructureChanged(e);
}
}
}

private boolean applyFilter(Filter filter, TreePath path, Object node, ArrayList expand) {
int count = model.getChildCount(node);
int[] viewToModel = null;
int viewIndex = 0;
TreePath parent = null;
for (int i=0; i

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
kleopatra
Offline
Joined: 2003-06-11

cool! Just ... a couple of comments after a not too deep look, admittedly

> Since I had sort in the name, I figured I might as
> well actually do some sorting. One thing that has
> bugged me about JTable's "RowSorter" is that it isn't
> just a sorter but a sorter/filter.

Maybe not getting entirely what you are saying: the RowSorter is about sorting only, its default implementation adds filtering. Which is weird enough, as client code has to code against that implementation instead of against an interface. That's why SwingX adds another a SortController interface which is roughly "DefaultRowSorter - RowSorter"

> instead. The implementation doesn't require any
> subclassing of a JTree, but don't be fooled - it is
> completely view based which should be clear in the
> constructor signature:
>
> TreeModelTransformer(JTree, TreeModel)
>

followed by a

[code]
tree.setModel(treeModelTransformer)
[/code]

that's what I call model-based ;-) The JTree only sees the wrapper model around the "real" model, just the same as the ol' TableSorter (pre table view sorting). Mind, that's not a bad idea (glazedlists do it all the time and excellently) and maybe the only thingy that can be done on hierarchical structures - it just isn't view-based. Let's keep the terminology clear. Tried to visualize the difference a couple of years ago:

https://swingx.dev.java.net/files/documents/2981/80092/swingx_beyond_com...

A defining streak of view-based sorting/filtering is that the view (the party with the J in front) is in the controlling center, so naturally, it must be subclassed to do it's stuff (keep all internal state, f.i. selection, in synch in terms of view coordinates). This shields all clients which talk to the data through the component only, that is don't access the model directly, from the underlying complexities.

A minor issue in your transformer: better let it use a Collator as fall-back comparator instead of toString.compare - which on first try fooled me into thinking there was something wrong on insert, because the latter is not locale-aware ;-)

Keep up the good work!
Jeanette

aephyr
Offline
Joined: 2009-11-20

> followed by a
>
> [code]
> tree.setModel(treeModelTransformer)
> [/code]
>
> that's what I call model-based ;-) The JTree only
> sees the wrapper model around the "real" model, just
> the same as the ol' TableSorter (pre table view
> sorting). Mind, that's not a bad idea (glazedlists do
> it all the time and excellently) and maybe the only
> thingy that can be done on hierarchical structures -
> it just isn't view-based. Let's keep the terminology
> clear.

I suppose "coupled to a view" would be better terminology then. The point I meant to make is that TreeModelTransformer isn't a "true" model in the sense that models are shareable between views. A view-based implementation as you have defined below isn't actually possible with JTree because the UI accesses the model directly. I guess it is the same thing mentioned in your presentation about JList: "Traditionally has no delegate methods".

> Tried to visualize the difference a couple of
> years ago:
>
> https://swingx.dev.java.net/files/documents/2981/80092
> /swingx_beyond_components.pdf

Nice presentation! Is that a self portrait on page 2? ;)

>
> A defining streak of view-based sorting/filtering is
> that the view (the party with the J in front) is in
> the controlling center, so naturally, it must be
> subclassed to do it's stuff (keep all internal state,
> f.i. selection, in synch in terms of view
> coordinates). This shields all clients which talk to
> the data through the component only, that is don't
> access the model directly, from the underlying
> complexities.
>
> A minor issue in your transformer: better let it use
> a Collator as fall-back comparator instead of
> toString.compare - which on first try fooled me into
> thinking there was something wrong on insert, because
> the latter is not locale-aware ;-)

OK - I have made the change.

kleopatra
Offline
Joined: 2003-06-11

>
> I suppose "coupled to a view" would be better
> terminology then. The point I meant to make is that
> TreeModelTransformer isn't a "true" model in the
> sense that models are shareable between views.

fair enough - that clarifies our different perspectives.

> view-based implementation as you have defined below
> isn't actually possible with JTree because the UI
> accesses the model directly. I guess it is the same
> thing mentioned in your presentation about JList:
> "Traditionally has no delegate methods".
>

well, optimistic me regards that fact as just a short-coming of the current core implementation - SwingX' JXList has delegate methods and a ui which does not access the model directly :-) Could imagine to do something similar to JXTree/Table - much more work, though. Hmm ...

> Nice presentation! Is that a self portrait on page 2?
> ;)
>

LOL

Cheers
Jeanette

josevnz
Offline
Joined: 2003-07-08

Nice, thanks for sharing this!

aephyr
Offline
Joined: 2009-11-20

You are welcome - but be advised that tree model modification handling isn't stable yet - or at least not in the version that I am currently working with.

aephyr
Offline
Joined: 2009-11-20

Since I had sort in the name, I figured I might as well actually do some sorting. One thing that has bugged me about JTable's "RowSorter" is that it isn't just a sorter but a sorter/filter. Though you wouldn't know that it does filtering until you dig a little deeper. So I have used the Transformer label instead. The implementation doesn't require any subclassing of a JTree, but don't be fooled - it is completely view based which should be clear in the constructor signature:

TreeModelTransformer(JTree, TreeModel)

I suppose it isn't necessary for it to be coupled to a view if there was some type of TransformerListener but then it wouldn't work too brilliantly with models that load their structure on demand. As I have implemented it, only expanded nodes will be sorted so that unexpanded nodes aren't unnecessarily loaded (in my case usage, fully loading the entire hierarchy is very expensive endeavor).

Filtering is different. I suppose it too could be implement as the sorting is, but in my case usage, I want the filtering to cause the hierarchy to fully load. Perhaps the behavior could be toggled by a property (as well as for sorting too) - but since there were no comments/suggestions, I just implemented it how I wanted it implemented and only how I wanted it implemented :)

The JTree sorter/filter:
http://code.google.com/p/aephyr/source/browse/trunk/src/aephyr/swing/Tre...

Simple demonstration/Testing platform:
http://code.google.com/p/aephyr/source/browse/trunk/src/test/aephyr/swin...

aephyr
Offline
Joined: 2009-11-20

I've commited a rather important update. There was a memory leak in the previous version that was the source of some rather unpleasant exception whining. The leak has been patched up as far as I can tell from profiling and running the simulator in the TreeSort tester class.