Merge commit '868c706b81e33e99c5f57fb9fc200808e061c4bb'
[fanfix.git] / ui / TreeModelTransformer.java
1 /*
2 * This program is free software: you can redistribute it and/or modify
3 * it under the terms of the GNU Lesser General Public License as published
4 * by the Free Software Foundation, either version 3 of the License, or
5 * (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU Lesser General Public License for more details.
11 *
12 * You should have received a copy of the GNU Lesser General Public License
13 * along with this program. If not, see <http://www.gnu.org/licenses/>.
14 */
15 // Can be found at: https://code.google.com/archive/p/aephyr/source/default/source
16 // package aephyr.swing;
17 package be.nikiroo.utils.ui;
18
19 import java.text.Collator;
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collection;
23 import java.util.Collections;
24 import java.util.Comparator;
25 import java.util.Enumeration;
26 import java.util.HashSet;
27 import java.util.List;
28 import java.util.Map;
29 import java.util.HashMap;
30 import java.util.Iterator;
31 import java.util.regex.Matcher;
32 import java.util.regex.Pattern;
33
34 import javax.swing.JTree;
35 import javax.swing.SortOrder;
36 import javax.swing.event.EventListenerList;
37 import javax.swing.event.TreeExpansionEvent;
38 import javax.swing.event.TreeExpansionListener;
39 import javax.swing.event.TreeModelEvent;
40 import javax.swing.event.TreeModelListener;
41 import javax.swing.event.TreeWillExpandListener;
42 import javax.swing.tree.ExpandVetoException;
43 import javax.swing.tree.TreeModel;
44 import javax.swing.tree.TreePath;
45
46
47 public class TreeModelTransformer<N> implements TreeModel {
48
49 public TreeModelTransformer(JTree tree, TreeModel model) {
50 if (tree == null)
51 throw new IllegalArgumentException();
52 if (model == null)
53 throw new IllegalArgumentException();
54 this.tree = tree;
55 this.model = model;
56 handler = createHandler();
57 addListeners();
58 }
59
60 private JTree tree;
61
62 private TreeModel model;
63
64 private Handler handler;
65
66 private Filter<N> filter;
67
68 private TreePath filterStartPath;
69
70 private int filterDepthLimit;
71
72 private SortOrder sortOrder = SortOrder.UNSORTED;
73
74 private Map<Object,Converter> converters;
75
76 protected EventListenerList listenerList = new EventListenerList();
77
78 protected Handler createHandler() {
79 return new Handler();
80 }
81
82 protected void addListeners() {
83 tree.addTreeExpansionListener(handler);
84 model.addTreeModelListener(handler);
85 }
86
87 protected void removeListeners() {
88 tree.removeTreeExpansionListener(handler);
89 model.removeTreeModelListener(handler);
90 }
91
92 public void dispose() {
93 removeListeners();
94 }
95
96 public TreeModel getModel() {
97 return model;
98 }
99
100 private Converter getConverter(Object node) {
101 return converters == null ? null : converters.get(node);
102 }
103
104 int convertRowIndexToView(Object parent, int index) {
105 Converter converter = getConverter(parent);
106 if (converter != null)
107 return converter.convertRowIndexToView(index);
108 return index;
109 }
110
111 int convertRowIndexToModel(Object parent, int index) {
112 Converter converter = getConverter(parent);
113 if (converter != null)
114 return converter.convertRowIndexToModel(index);
115 return index;
116 }
117
118 @Override
119 public Object getChild(Object parent, int index) {
120 return model.getChild(parent, convertRowIndexToModel(parent, index));
121 }
122
123 @Override
124 public int getChildCount(Object parent) {
125 Converter converter = getConverter(parent);
126 if (converter != null)
127 return converter.getChildCount();
128 return model.getChildCount(parent);
129 }
130
131 @Override
132 public int getIndexOfChild(Object parent, Object child) {
133 int index = model.getIndexOfChild(parent, child);
134 if (index < 0)
135 return -1;
136 return convertRowIndexToView(parent, index);
137 }
138
139 @Override
140 public Object getRoot() {
141 return model.getRoot();
142 }
143
144 @Override
145 public boolean isLeaf(Object node) {
146 return model.isLeaf(node);
147 }
148
149 @Override
150 public void valueForPathChanged(TreePath path, Object newValue) {
151 model.valueForPathChanged(path, newValue);
152 }
153
154 @Override
155 public void addTreeModelListener(TreeModelListener l) {
156 listenerList.add(TreeModelListener.class, l);
157 }
158
159 @Override
160 public void removeTreeModelListener(TreeModelListener l) {
161 listenerList.remove(TreeModelListener.class, l);
162 }
163
164 /**
165 * Set the comparator that compares nodes in sorting.
166 * @param comparator
167 * @see #getComparator()
168 */
169 public void setComparator(Comparator<N> comparator) {
170 handler.setComparator(comparator);
171 }
172
173 /**
174 * @return comparator that compares nodes
175 * @see #setComparator(Comparator)
176 */
177 public Comparator<N> getComparator() {
178 return handler.getComparator();
179 }
180
181 public void setSortOrder(SortOrder newOrder) {
182 SortOrder oldOrder = sortOrder;
183 if (oldOrder == newOrder)
184 return;
185 sortOrder = newOrder;
186 ArrayList<TreePath> paths = null;
187 switch (newOrder) {
188 case ASCENDING:
189 if (oldOrder == SortOrder.DESCENDING) {
190 flip();
191 } else {
192 paths = sort();
193 }
194 break;
195 case DESCENDING:
196 if (oldOrder == SortOrder.ASCENDING) {
197 flip();
198 } else {
199 paths = sort();
200 }
201 break;
202 case UNSORTED:
203 unsort();
204 break;
205 }
206 fireTreeStructureChangedAndExpand(new TreePath(getRoot()), paths, true);
207 }
208
209 public SortOrder getSortOrder() {
210 return sortOrder;
211 }
212
213 public void toggleSortOrder() {
214 setSortOrder(sortOrder == SortOrder.ASCENDING ?
215 SortOrder.DESCENDING : SortOrder.ASCENDING);
216 }
217
218
219 /**
220 * Flip all sorted paths.
221 */
222 private void flip() {
223 for (Converter c : converters.values()) {
224 flip(c.viewToModel);
225 }
226 }
227
228 /**
229 * Flip array.
230 * @param array
231 */
232 private static void flip(int[] array) {
233 for (int left=0, right=array.length-1;
234 left<right; left++, right--) {
235 int tmp = array[left];
236 array[left] = array[right];
237 array[right] = tmp;
238 }
239 }
240
241 private void unsort() {
242 if (filter == null) {
243 converters = null;
244 } else {
245 Iterator<Converter> cons = converters.values().iterator();
246 while (cons.hasNext()) {
247 Converter converter = cons.next();
248 if (!converter.isFiltered()) {
249 cons.remove();
250 } else {
251 Arrays.sort(converter.viewToModel);
252 }
253 }
254 }
255 }
256
257 /**
258 * Sort root and expanded descendants.
259 * @return list of paths that were sorted
260 */
261 private ArrayList<TreePath> sort() {
262 if (converters == null)
263 converters = createConvertersMap(); //new IdentityHashMap<Object,Converter>();
264 return sortHierarchy(new TreePath(model.getRoot()));
265 }
266
267 /**
268 * Sort path and expanded descendants.
269 * @param path
270 * @return list of paths that were sorted
271 */
272 private ArrayList<TreePath> sortHierarchy(TreePath path) {
273 ValueIndexPair<N>[] pairs = createValueIndexPairArray(20);
274 ArrayList<TreePath> list = new ArrayList<TreePath>();
275 pairs = sort(path.getLastPathComponent(), pairs);
276 list.add(path);
277 Enumeration<TreePath> paths = tree.getExpandedDescendants(path);
278 if (paths != null)
279 while (paths.hasMoreElements()) {
280 path = paths.nextElement();
281 pairs = sort(path.getLastPathComponent(), pairs);
282 list.add(path);
283 }
284 return list;
285 }
286
287 private ValueIndexPair<N>[] sort(Object node, ValueIndexPair<N>[] pairs) {
288 Converter converter = getConverter(node);
289 TreeModel mdl = model;
290 int[] vtm;
291 if (converter != null) {
292 vtm = converter.viewToModel;
293 if (pairs.length < vtm.length)
294 pairs = createValueIndexPairArray(vtm.length);
295 for (int i=vtm.length; --i>=0;) {
296 int idx = vtm[i];
297 pairs[i].index = idx;
298 pairs[i].value = (N)mdl.getChild(node, idx);
299 }
300 } else {
301 int count = mdl.getChildCount(node);
302 if (count <= 0)
303 return pairs;
304 if (pairs.length < count)
305 pairs = createValueIndexPairArray(count);
306 for (int i=count; --i>=0;) {
307 pairs[i].index = i;
308 pairs[i].value = (N)mdl.getChild(node, i);
309 }
310 vtm = new int[count];
311 }
312 Arrays.sort(pairs, 0, vtm.length, handler);
313 for (int i=vtm.length; --i>=0;)
314 vtm[i] = pairs[i].index;
315 if (converter == null) {
316 converters.put(node, new Converter(vtm, false));
317 }
318 if (sortOrder == SortOrder.DESCENDING)
319 flip(vtm);
320 return pairs;
321 }
322
323 private ValueIndexPair<N>[] createValueIndexPairArray(int len) {
324 ValueIndexPair<N>[] pairs = new ValueIndexPair[len];
325 for (int i=len; --i>=0;)
326 pairs[i] = new ValueIndexPair<N>();
327 return pairs;
328 }
329
330 public void setFilter(Filter<N> filter) {
331 setFilter(filter, null);
332 }
333
334 public void setFilter(Filter<N> filter, TreePath startingPath) {
335 setFilter(filter, null, -1);
336 }
337
338 public void setFilter(Filter<N> filter, TreePath startingPath, int depthLimit) {
339 if (filter == null && startingPath != null)
340 throw new IllegalArgumentException();
341 if (startingPath != null && startingPath.getPathCount() == 1)
342 startingPath = null;
343 Filter<N> oldFilter = this.filter;
344 TreePath oldStartPath = filterStartPath;
345 this.filter = filter;
346 filterStartPath = startingPath;
347 filterDepthLimit = depthLimit;
348 applyFilter(oldFilter, oldStartPath, null, true);
349 }
350
351 public Filter<N> getFilter() {
352 return filter;
353 }
354
355 public TreePath getFilterStartPath() {
356 return filterStartPath;
357 }
358
359 private void applyFilter(Filter<N> oldFilter, TreePath oldStartPath, Collection<TreePath> expanded, boolean sort) {
360 TreePath startingPath = filterStartPath;
361 ArrayList<TreePath> expand = null;
362 if (filter == null) {
363 converters = null;
364 } else {
365 if (converters == null || startingPath == null) {
366 converters = createConvertersMap();
367 } else if (oldFilter != null) {
368 // unfilter the oldStartPath if oldStartPath isn't descendant of startingPath
369 if (oldStartPath == null) {
370 converters = createConvertersMap();
371 fireTreeStructureChangedAndExpand(new TreePath(getRoot()), null, true);
372 } else if (!startingPath.isDescendant(oldStartPath)) {
373 Object node = oldStartPath.getLastPathComponent();
374 handler.removeConverter(getConverter(node), node);
375 fireTreeStructureChangedAndExpand(oldStartPath, null, true);
376 }
377 }
378 expand = new ArrayList<TreePath>();
379 TreePath path = startingPath != null ? startingPath : new TreePath(getRoot());
380 if (!applyFilter(filter, path, expand, filterDepthLimit)) {
381 converters.put(path.getLastPathComponent(), new Converter(Converter.EMPTY, true));
382 }
383 }
384 if (startingPath == null)
385 startingPath = new TreePath(getRoot());
386 fireTreeStructureChanged(startingPath);
387 if (expanded != null)
388 expand.retainAll(expanded);
389 expandPaths(expand);
390 if (sort && sortOrder != SortOrder.UNSORTED) {
391 if (filter == null)
392 converters = createConvertersMap();
393 if (startingPath.getPathCount() > 1 && oldFilter != null) {
394 // upgrade startingPath or sort oldStartPath
395 if (oldStartPath == null) {
396 startingPath = new TreePath(getRoot());
397 } else if (oldStartPath.isDescendant(startingPath)) {
398 startingPath = oldStartPath;
399 } else if (!startingPath.isDescendant(oldStartPath)) {
400 expand = sortHierarchy(oldStartPath);
401 fireTreeStructureChanged(oldStartPath);
402 expandPaths(expand);
403 }
404 }
405 expand = sortHierarchy(startingPath);
406 fireTreeStructureChanged(startingPath);
407 expandPaths(expand);
408 }
409
410 }
411
412 private boolean applyFilter(Filter<N> filter, TreePath path, ArrayList<TreePath> expand) {
413 int depthLimit = filterDepthLimit;
414 if (depthLimit >= 0) {
415 depthLimit -= filterStartPath.getPathCount() - path.getPathCount();
416 if (depthLimit <= 0)
417 return false;
418 }
419 return applyFilter(filter, path, expand, depthLimit);
420 }
421
422 private boolean applyFilter(Filter<N> filter, TreePath path, ArrayList<TreePath> expand, int depthLimit) {
423 Object node = path.getLastPathComponent();
424 int count = model.getChildCount(node);
425 int[] viewToModel = null;
426 int viewIndex = 0;
427 boolean needsExpand = false;
428 boolean isExpanded = false;
429 if (depthLimit > 0)
430 depthLimit--;
431 for (int i=0; i<count; i++) {
432 Object child = model.getChild(node, i);
433 boolean leaf = model.isLeaf(child);
434 if (filter.acceptNode(path, (N)child, leaf)) {
435 if (viewToModel == null)
436 viewToModel = new int[count-i];
437 viewToModel[viewIndex++] = i;
438 needsExpand = true;
439 } else if (depthLimit != 0 && !leaf) {
440 if (applyFilter(filter, path.pathByAddingChild(child), expand, depthLimit)) {
441 if (viewToModel == null)
442 viewToModel = new int[count-i];
443 viewToModel[viewIndex++] = i;
444 isExpanded = true;
445 }
446 }
447 }
448 if (needsExpand && expand != null && !isExpanded && path.getPathCount() > 1) {
449 expand.add(path);
450 }
451 if (viewToModel != null) {
452 if (viewIndex < viewToModel.length)
453 viewToModel = Arrays.copyOf(viewToModel, viewIndex);
454 // a node must have a converter to signify that tree modifications
455 // need to query the filter, so have to put in converter
456 // even if viewIndex == viewToModel.length
457 converters.put(node, new Converter(viewToModel, true));
458 return true;
459 }
460 return false;
461 }
462
463
464 private void expandPaths(ArrayList<TreePath> paths) {
465 if (paths == null || paths.isEmpty())
466 return;
467 JTree tre = tree;
468 for (TreePath path : paths)
469 tre.expandPath(path);
470 }
471
472
473 private void fireTreeStructureChangedAndExpand(TreePath path, ArrayList<TreePath> list, boolean retainSelection) {
474 Enumeration<TreePath> paths = list != null ?
475 Collections.enumeration(list) : tree.getExpandedDescendants(path);
476 TreePath[] sel = retainSelection ? tree.getSelectionPaths() : null;
477 fireTreeStructureChanged(path);
478 if (paths != null)
479 while (paths.hasMoreElements())
480 tree.expandPath(paths.nextElement());
481 if (sel != null)
482 tree.setSelectionPaths(sel);
483 }
484
485
486
487 protected void fireTreeStructureChanged(TreePath path) {
488 Object[] listeners = listenerList.getListenerList();
489 TreeModelEvent e = null;
490 for (int i = listeners.length-2; i>=0; i-=2) {
491 if (listeners[i]==TreeModelListener.class) {
492 if (e == null)
493 e = new TreeModelEvent(this, path, null, null);
494 ((TreeModelListener)listeners[i+1]).treeStructureChanged(e);
495 }
496 }
497 }
498
499 protected void fireTreeNodesChanged(TreePath path, int[] childIndices, Object[] childNodes) {
500 Object[] listeners = listenerList.getListenerList();
501 TreeModelEvent e = null;
502 for (int i = listeners.length-2; i>=0; i-=2) {
503 if (listeners[i]==TreeModelListener.class) {
504 if (e == null)
505 e = new TreeModelEvent(this, path, childIndices, childNodes);
506 ((TreeModelListener)listeners[i+1]).treeNodesChanged(e);
507 }
508 }
509 }
510
511 protected void fireTreeNodesInserted(TreePath path, int[] childIndices, Object[] childNodes) {
512 Object[] listeners = listenerList.getListenerList();
513 TreeModelEvent e = null;
514 for (int i = listeners.length-2; i>=0; i-=2) {
515 if (listeners[i]==TreeModelListener.class) {
516 if (e == null)
517 e = new TreeModelEvent(this, path, childIndices, childNodes);
518 ((TreeModelListener)listeners[i+1]).treeNodesInserted(e);
519 }
520 }
521 }
522
523 protected void fireTreeNodesRemoved(TreePath path, int[] childIndices, Object[] childNodes) {
524 Object[] listeners = listenerList.getListenerList();
525 TreeModelEvent e = null;
526 for (int i = listeners.length-2; i>=0; i-=2) {
527 if (listeners[i]==TreeModelListener.class) {
528 if (e == null)
529 e = new TreeModelEvent(this, path, childIndices, childNodes);
530 ((TreeModelListener)listeners[i+1]).treeNodesRemoved(e);
531 }
532 }
533 }
534
535
536 protected class Handler implements Comparator<ValueIndexPair<N>>,
537 TreeModelListener, TreeExpansionListener {
538
539 private Comparator<N> comparator;
540
541 private Collator collator = Collator.getInstance();
542
543 void setComparator(Comparator<N> cmp) {
544 comparator = cmp;
545 collator = cmp == null ? Collator.getInstance() : null;
546 }
547
548 Comparator<N> getComparator() {
549 return comparator;
550 }
551
552 // TODO, maybe switch to TreeWillExpandListener?
553 // TreeExpansionListener was used in case an expanded node
554 // had children that would also be expanded, but it is impossible
555 // for hidden nodes' expansion state to survive a SortOrder change
556 // since they are all erased when the tree structure change event
557 // is fired after changing the SortOrder.
558
559 @Override
560 public void treeCollapsed(TreeExpansionEvent e) {}
561
562 @Override
563 public void treeExpanded(TreeExpansionEvent e) {
564 if (sortOrder != SortOrder.UNSORTED) {
565 TreePath path = e.getPath();
566 Converter converter = getConverter(path.getLastPathComponent());
567 if (converter == null) {
568 ArrayList<TreePath> paths = sortHierarchy(path);
569 fireTreeStructureChangedAndExpand(path, paths, false);
570 }
571 }
572 }
573
574 private boolean isFiltered(Object node) {
575 Converter c = getConverter(node);
576 return c == null ? false : c.isFiltered();
577 }
578
579 private boolean acceptable(TreePath path, Object[] childNodes, int index, ArrayList<TreePath> expand) {
580 return acceptable(path, childNodes, index) ||
581 applyFilter(filter, path.pathByAddingChild(childNodes[index]), expand);
582 }
583
584 @Override
585 public void treeNodesChanged(TreeModelEvent e) {
586 treeNodesChanged(e.getTreePath(), e.getChildIndices(), e.getChildren());
587 }
588
589 protected void treeNodesChanged(TreePath path, int[] childIndices, Object[] childNodes) {
590 if (childIndices == null) {
591 // path should be root path
592 // reapply filter
593 if (filter != null)
594 applyFilter(null, null, null, true);
595 return;
596 }
597 Converter converter = getConverter(path.getLastPathComponent());
598 ArrayList<TreePath> expand = null;
599 if (converter != null) {
600 expand = new ArrayList<TreePath>();
601 int childIndex = 0;
602 for (int i=0; i<childIndices.length; i++) {
603 int idx = converter.convertRowIndexToView(childIndices[i]);
604 if (idx >= 0) {
605 // see if the filter dislikes the nodes new state
606 if (converter.isFiltered() &&
607 !isFiltered(childNodes[i]) &&
608 !acceptable(path, childNodes, i)) {
609 // maybe it likes a child nodes state
610 if (!applyFilter(filter, path.pathByAddingChild(childNodes[i]), expand))
611 remove(path, childNodes[i]);
612 continue;
613 }
614 childNodes[childIndex] = childNodes[i];
615 childIndices[childIndex++] = idx;
616 } else if (acceptable(path, childNodes, i, expand)) {
617 int viewIndex = insert(path.getLastPathComponent(),
618 childNodes[i], childIndices[i], converter);
619 fireTreeNodesInserted(path, indices(viewIndex), nodes(childNodes[i]));
620 }
621 }
622 if (childIndex == 0) {
623 maybeFireStructureChange(path, expand);
624 return;
625 }
626 if (sortOrder != SortOrder.UNSORTED && converter.getChildCount() > 1) {
627 sort(path.getLastPathComponent(), createValueIndexPairArray(converter.getChildCount()));
628 fireTreeStructureChangedAndExpand(path, null, true);
629 expandPaths(expand);
630 return;
631 }
632 if (childIndex != childIndices.length) {
633 childIndices = Arrays.copyOf(childIndices, childIndex);
634 childNodes = Arrays.copyOf(childNodes, childIndex);
635 }
636 } else if (filter != null && isFilteredOut(path)) {
637 // see if the filter likes the nodes new states
638 expand = new ArrayList<TreePath>();
639 int[] vtm = null;
640 int idx = 0;
641 for (int i=0; i<childIndices.length; i++) {
642 if (acceptable(path, childNodes, i, expand)) {
643 if (vtm == null)
644 vtm = new int[childIndices.length-i];
645 vtm[idx++] = childIndices[i];
646 }
647 }
648 // filter in path if appropriate
649 if (vtm != null)
650 filterIn(vtm, idx, path, expand);
651 return;
652 }
653 // must fire tree nodes changed even if a
654 // structure change will be fired because the
655 // expanded paths need to be updated first
656 fireTreeNodesChanged(path, childIndices, childNodes);
657 maybeFireStructureChange(path, expand);
658 }
659
660 /**
661 * Helper method for treeNodesChanged...
662 * @param path
663 * @param expand
664 */
665 private void maybeFireStructureChange(TreePath path, ArrayList<TreePath> expand) {
666 if (expand != null && !expand.isEmpty()) {
667 Enumeration<TreePath> expanded = tree.getExpandedDescendants(path);
668 fireTreeStructureChanged(path);
669 if (expanded != null)
670 while (expanded.hasMoreElements())
671 tree.expandPath(expanded.nextElement());
672 expandPaths(expand);
673 }
674 }
675
676 @Override
677 public void treeNodesInserted(TreeModelEvent e) {
678 treeNodesInserted(e.getTreePath(), e.getChildIndices(), e.getChildren());
679 }
680
681 protected void treeNodesInserted(TreePath path, int[] childIndices, Object[] childNodes) {
682 Object parent = path.getLastPathComponent();
683 Converter converter = getConverter(parent);
684 ArrayList<TreePath> expand = null;
685 if (converter != null) {
686 // if (childIndices.length > 3 && !converter.isFiltered()
687 // && childIndices.length > converter.getChildCount()/10) {
688 // TreePath expand = sortHierarchy(path);
689 // fireTreeStructureChangedAndExpand(expand);
690 // return;
691 // }
692 int childIndex = 0;
693 for (int i=0; i<childIndices.length; i++) {
694 if (converter.isFiltered()) {
695 // path hasn't met the filter criteria, so childNodes must be filtered
696 if (expand == null)
697 expand = new ArrayList<TreePath>();
698 if (!applyFilter(filter, path.pathByAddingChild(childNodes[i]), expand))
699 continue;
700 }
701 // shift the appropriate cached modelIndices
702 int[] vtm = converter.viewToModel;
703 int modelIndex = childIndices[i];
704 for (int j=vtm.length; --j>=0;) {
705 if (vtm[j] >= modelIndex)
706 vtm[j] += 1;
707 }
708 // insert modelIndex to converter
709 int viewIndex = insert(parent, childNodes[i], modelIndex, converter);
710 childNodes[childIndex] = childNodes[i];
711 childIndices[childIndex++] = viewIndex;
712 }
713 if (childIndex == 0)
714 return;
715 if (childIndex != childIndices.length) {
716 childIndices = Arrays.copyOf(childIndices, childIndex);
717 childNodes = Arrays.copyOf(childNodes, childIndex);
718 }
719 if (childIndex > 1 && sortOrder != SortOrder.UNSORTED) {
720 sort(childIndices, childNodes);
721 }
722 } else if (filter != null && isFilteredOut(path)) {
723 // apply filter to inserted nodes
724 int[] vtm = null;
725 int idx = 0;
726 expand = new ArrayList<TreePath>();
727 for (int i=0; i<childIndices.length; i++) {
728 if (acceptable(path, childNodes, i, expand)) {
729 if (vtm == null)
730 vtm = new int[childIndices.length-i];
731 vtm[idx++] = childIndices[i];
732 }
733 }
734 // filter in path if appropriate
735 if (vtm != null)
736 filterIn(vtm, idx, path, expand);
737 return;
738 }
739 fireTreeNodesInserted(path, childIndices, childNodes);
740 expandPaths(expand);
741 }
742
743 @Override
744 public void treeNodesRemoved(TreeModelEvent e) {
745 treeNodesRemoved(e.getTreePath(), e.getChildIndices(), e.getChildren());
746 }
747
748
749 private boolean isFilterStartPath(TreePath path) {
750 if (filterStartPath == null)
751 return path.getPathCount() == 1;
752 return filterStartPath.equals(path);
753 }
754
755 protected void treeNodesRemoved(TreePath path, int[] childIndices, Object[] childNodes) {
756 Object parent = path.getLastPathComponent();
757 Converter converter = getConverter(parent);
758 if (converter != null) {
759 int len = 0;
760 for (int i=0; i<childNodes.length; i++) {
761 removeConverter(childNodes[i]);
762 int viewIndex = converter.convertRowIndexToView(childIndices[i]);
763 if (viewIndex >= 0) {
764 childNodes[len] = childNodes[i];
765 childIndices[len++] = viewIndex;
766 }
767 }
768 if (len == 0)
769 return;
770 if (converter.isFiltered() && converter.getChildCount() == len) {
771 ArrayList<TreePath> expand = new ArrayList<TreePath>();
772 if (applyFilter(filter, path, expand)) {
773 expand.retainAll(getExpandedPaths(path));
774 if (sortOrder != SortOrder.UNSORTED)
775 sortHierarchy(path);
776 fireTreeStructureChangedAndExpand(path, expand, true);
777 } else if (isFilterStartPath(path)) {
778 converters.put(parent, new Converter(Converter.EMPTY, true));
779 fireTreeStructureChanged(path);
780 } else {
781 remove(path.getParentPath(), parent);
782 }
783 return;
784 }
785 if (len != childIndices.length) {
786 childIndices = Arrays.copyOf(childIndices, len);
787 childNodes = Arrays.copyOf(childNodes, len);
788 }
789 if (len > 1 && sortOrder != SortOrder.UNSORTED) {
790 sort(childIndices, childNodes);
791 }
792 if (childIndices.length == 1) {
793 converter.remove(converter.convertRowIndexToModel(childIndices[0]));
794 } else {
795 converter.remove(childIndices);
796 }
797 } else if (filter != null && isFilteredOut(path)) {
798 return;
799 }
800 fireTreeNodesRemoved(path, childIndices, childNodes);
801 }
802
803 private Collection<TreePath> getExpandedPaths(TreePath path) {
804 Enumeration<TreePath> en = tree.getExpandedDescendants(path);
805 if (en == null)
806 return Collections.emptySet();
807 HashSet<TreePath> expanded = new HashSet<TreePath>();
808 while (en.hasMoreElements())
809 expanded.add(en.nextElement());
810 return expanded;
811 }
812
813 @Override
814 public void treeStructureChanged(TreeModelEvent e) {
815 if (converters != null) {
816 // not enough information to properly clean up
817 // reapply filter/sort
818 converters = createConvertersMap();
819 TreePath[] sel = tree.getSelectionPaths();
820 if (filter != null) {
821 applyFilter(null, null, getExpandedPaths(new TreePath(getRoot())), false);
822 }
823 if (sortOrder != SortOrder.UNSORTED) {
824 TreePath path = new TreePath(getRoot());
825 ArrayList<TreePath> expand = sortHierarchy(path);
826 fireTreeStructureChangedAndExpand(path, expand, false);
827 }
828 if (sel != null) {
829 tree.clearSelection();
830 TreePath changedPath = e.getTreePath();
831 for (TreePath path : sel) {
832 if (!changedPath.isDescendant(path))
833 tree.addSelectionPath(path);
834 }
835 }
836 } else {
837 fireTreeStructureChanged(e.getTreePath());
838 }
839 }
840
841
842 @Override
843 public final int compare(ValueIndexPair<N> a, ValueIndexPair<N> b) {
844 return compareNodes(a.value, b.value);
845 }
846
847
848 protected int compareNodes(N a, N b) {
849 if (comparator != null)
850 return comparator.compare(a, b);
851 return collator.compare(a.toString(), b.toString());
852 }
853
854 private void removeConverter(Object node) {
855 Converter c = getConverter(node);
856 if (c != null)
857 removeConverter(c, node);
858 }
859
860 private void removeConverter(Converter converter, Object node) {
861 for (int i=converter.getChildCount(); --i>=0;) {
862 int index = converter.convertRowIndexToModel(i);
863 Object child = model.getChild(node, index);
864 Converter c = getConverter(child);
865 if (c != null)
866 removeConverter(c, child);
867 }
868 converters.remove(node);
869 }
870
871 private boolean isFilteredOut(TreePath path) {
872 if (filterStartPath != null && !filterStartPath.isDescendant(path))
873 return false;
874 TreePath parent = path.getParentPath();
875 // root should always have a converter if filter is non-null,
876 // so if parent is ever null, there is a bug somewhere else
877 Converter c = getConverter(parent.getLastPathComponent());
878 if (c != null) {
879 return getIndexOfChild(
880 parent.getLastPathComponent(),
881 path.getLastPathComponent()) < 0;
882 }
883 return isFilteredOut(parent);
884 }
885
886 private void filterIn(int[] vtm, int vtmLength, TreePath path, ArrayList<TreePath> expand) {
887 Object node = path.getLastPathComponent();
888 if (vtmLength != vtm.length)
889 vtm = Arrays.copyOf(vtm, vtmLength);
890 Converter converter = new Converter(vtm, true);
891 converters.put(node, converter);
892 insert(path.getParentPath(), node);
893 tree.expandPath(path);
894 expandPaths(expand);
895 }
896
897 private boolean acceptable(TreePath path, Object[] nodes, int index) {
898 Object node = nodes[index];
899 return filter.acceptNode(path, (N)node, model.isLeaf(node));
900 }
901
902 private int ascInsertionIndex(int[] vtm, Object parent, N node, int idx) {
903 for (int i=vtm.length; --i>=0;) {
904 int cmp = compareNodes(node, (N)model.getChild(parent, vtm[i]));
905 if (cmp > 0 || (cmp == 0 && idx > vtm[i])) {
906 return i+1;
907 }
908 }
909 return 0;
910 }
911
912
913 private int dscInsertionIndex(int[] vtm, Object parent, N node, int idx) {
914 for (int i=vtm.length; --i>=0;) {
915 int cmp = compareNodes(node, (N)model.getChild(parent, vtm[i]));
916 if (cmp < 0) {
917 return i+1;
918 } else if (cmp == 0 && idx < vtm[i]) {
919 return i;
920 }
921 }
922 return 0;
923 }
924
925
926 /**
927 * Inserts the specified path and node and any parent paths as necessary.
928 * <p>
929 * Fires appropriate event.
930 * @param path
931 * @param node
932 */
933 private void insert(TreePath path, Object node) {
934 Object parent = path.getLastPathComponent();
935 Converter converter = converters.get(parent);
936 int modelIndex = model.getIndexOfChild(parent, node);
937 if (converter == null) {
938 converter = new Converter(indices(modelIndex), true);
939 converters.put(parent, converter);
940 insert(path.getParentPath(), parent);
941 } else {
942 int viewIndex = insert(parent, node, modelIndex, converter);
943 fireTreeNodesInserted(path, indices(viewIndex), nodes(node));
944 }
945 }
946
947 /**
948 * Inserts node into parent in correct sort order.
949 * <p>
950 * Responsibility of caller to fire appropriate event with the returned viewIndex.
951 * @param path
952 * @param node
953 * @param modelIndex
954 * @param converter
955 * @return viewIndex
956 */
957 private int insert(Object parent, Object node, int modelIndex, Converter converter) {
958 int[] vtm = converter.viewToModel;
959 int viewIndex;
960 switch (sortOrder) {
961 case ASCENDING:
962 viewIndex = ascInsertionIndex(vtm, parent, (N)node, modelIndex);
963 break;
964 case DESCENDING:
965 viewIndex = dscInsertionIndex(vtm, parent, (N)node, modelIndex);
966 break;
967 default: case UNSORTED:
968 viewIndex = unsortedInsertionIndex(vtm, modelIndex);
969 break;
970 }
971 int[] a = new int[vtm.length+1];
972 System.arraycopy(vtm, 0, a, 0, viewIndex);
973 System.arraycopy(vtm, viewIndex, a, viewIndex+1, vtm.length-viewIndex);
974 a[viewIndex] = modelIndex;
975 converter.viewToModel = a;
976 return viewIndex;
977 }
978
979 private void remove(TreePath path, Object node) {
980 Object parent = path.getLastPathComponent();
981 if (path.getPathCount() == 1 || (filterStartPath != null && filterStartPath.equals(path))) {
982 removeConverter(node);
983 converters.put(parent, new Converter(Converter.EMPTY, true));
984 fireTreeNodesRemoved(path, indices(0), nodes(node));
985 return;
986 }
987 Converter converter = converters.get(parent);
988 int modelIndex = model.getIndexOfChild(parent, node);
989 int viewIndex = converter.remove(modelIndex);
990 switch (viewIndex) {
991 default:
992 removeConverter(node);
993 fireTreeNodesRemoved(path, indices(viewIndex), nodes(node));
994 break;
995 case Converter.ONLY_INDEX:
996 // if (path.getParentPath() == null) {
997 // // reached filter root
998 // removeConverter(node);
999 // converters.put(parent, new Converter(Converter.EMPTY, true));
1000 // fireTreeNodesRemoved(path, indices(0), nodes(node));
1001 // return;
1002 // }
1003 remove(path.getParentPath(), parent);
1004 break;
1005 case Converter.INDEX_NOT_FOUND:
1006 removeConverter(node);
1007 }
1008 }
1009
1010
1011
1012 }
1013
1014
1015
1016 private static int unsortedInsertionIndex(int[] vtm, int idx) {
1017 for (int i=vtm.length; --i>=0;)
1018 if (vtm[i] < idx)
1019 return i+1;
1020 return 0;
1021 }
1022
1023 private static void sort(int[] childIndices, Object[] childNodes) {
1024 int len = childIndices.length;
1025 ValueIndexPair[] pairs = new ValueIndexPair[len];
1026 for (int i=len; --i>=0;)
1027 pairs[i] = new ValueIndexPair<Object>(childIndices[i], childNodes[i]);
1028 Arrays.sort(pairs);
1029 for (int i=len; --i>=0;) {
1030 childIndices[i] = pairs[i].index;
1031 childNodes[i] = pairs[i].value;
1032 }
1033 }
1034
1035 private static int[] indices(int...indices) {
1036 return indices;
1037 }
1038
1039 private static Object[] nodes(Object...nodes) {
1040 return nodes;
1041 }
1042
1043
1044
1045
1046 /**
1047 * This class has a dual purpose, both related to comparing/sorting.
1048 * <p>
1049 * The Handler class sorts an array of ValueIndexPair based on the value.
1050 * Used for sorting the view.
1051 * <p>
1052 * ValueIndexPair sorts itself based on the index.
1053 * Used for sorting childIndices for fire* methods.
1054 */
1055 private static class ValueIndexPair<N> implements Comparable<ValueIndexPair<N>> {
1056 ValueIndexPair() {}
1057
1058 ValueIndexPair(int idx, N val) {
1059 index = idx;
1060 value = val;
1061 }
1062
1063 N value;
1064
1065 int index;
1066
1067 public int compareTo(ValueIndexPair<N> o) {
1068 return index - o.index;
1069 }
1070 }
1071
1072 private static class Converter {
1073
1074 static final int[] EMPTY = new int[0];
1075
1076 static final int ONLY_INDEX = -2;
1077
1078 static final int INDEX_NOT_FOUND = -1;
1079
1080 Converter(int[] vtm, boolean filtered) {
1081 viewToModel = vtm;
1082 isFiltered = filtered;
1083 }
1084
1085 private int[] viewToModel;
1086
1087 private boolean isFiltered;
1088
1089 // public boolean equals(Converter conv) {
1090 // if (conv == null)
1091 // return false;
1092 // if (isFiltered != conv.isFiltered)
1093 // return false;
1094 // return Arrays.equals(viewToModel, conv.viewToModel);
1095 // }
1096
1097 boolean isFiltered() {
1098 return isFiltered;
1099 }
1100
1101 void remove(int viewIndices[]) {
1102 int len = viewToModel.length - viewIndices.length;
1103 if (len == 0) {
1104 viewToModel = EMPTY;
1105 } else {
1106 int[] oldVTM = viewToModel;
1107 int[] newVTM = new int[len];
1108 for (int oldIndex=0, newIndex=0, removeIndex=0;
1109 newIndex<newVTM.length;
1110 newIndex++, oldIndex++) {
1111 while (removeIndex < viewIndices.length && oldIndex == viewIndices[removeIndex]) {
1112 int idx = oldVTM[oldIndex];
1113 removeIndex++;
1114 oldIndex++;
1115 for (int i=newIndex; --i>=0;)
1116 if (newVTM[i] > idx)
1117 newVTM[i]--;
1118 for (int i=oldIndex; i<oldVTM.length; i++)
1119 if (oldVTM[i] > idx)
1120 oldVTM[i]--;
1121 }
1122 newVTM[newIndex] = oldVTM[oldIndex];
1123 }
1124 viewToModel = newVTM;
1125 }
1126 }
1127
1128 /**
1129 * @param modelIndex
1130 * @return viewIndex that was removed<br>
1131 * or <code>ONLY_INDEX</code> if the modelIndex is the only one in the view<br>
1132 * or <code>INDEX_NOT_FOUND</code> if the modelIndex is not in the view
1133 */
1134 int remove(int modelIndex) {
1135 int[] vtm = viewToModel;
1136 for (int i=vtm.length; --i>=0;) {
1137 if (vtm[i] > modelIndex) {
1138 vtm[i] -= 1;
1139 } else if (vtm[i] == modelIndex) {
1140 if (vtm.length == 1) {
1141 viewToModel = EMPTY;
1142 return ONLY_INDEX;
1143 }
1144 int viewIndex = i;
1145 while (--i>=0) {
1146 if (vtm[i] > modelIndex)
1147 vtm[i] -= 1;
1148 }
1149 int[] a = new int[vtm.length-1];
1150 if (viewIndex > 0)
1151 System.arraycopy(vtm, 0, a, 0, viewIndex);
1152 int len = a.length-viewIndex;
1153 if (len > 0)
1154 System.arraycopy(vtm, viewIndex+1, a, viewIndex, len);
1155 viewToModel = a;
1156 return viewIndex;
1157 }
1158 }
1159 return INDEX_NOT_FOUND;
1160 }
1161
1162
1163 int getChildCount() {
1164 return viewToModel.length;
1165 }
1166
1167 /**
1168 * @param modelIndex
1169 * @return viewIndex corresponding to modelIndex<br>
1170 * or <code>INDEX_NOT_FOUND</code> if the modelIndex is not in the view
1171 */
1172 int convertRowIndexToView(int modelIndex) {
1173 int[] vtm = viewToModel;
1174 for (int i=vtm.length; --i>=0;) {
1175 if (vtm[i] == modelIndex)
1176 return i;
1177 }
1178 return INDEX_NOT_FOUND;
1179 }
1180
1181 int convertRowIndexToModel(int viewIndex) {
1182 return viewToModel[viewIndex];
1183 }
1184 }
1185
1186 public interface Filter<N> {
1187 boolean acceptNode(TreePath parent, N node, boolean leaf);
1188 }
1189
1190 public static class RegexFilter<N> implements Filter<N> {
1191
1192 public RegexFilter(Pattern pattern, boolean leaf) {
1193 matcher = pattern.matcher("");
1194 leafOnly = leaf;
1195 }
1196
1197 private Matcher matcher;
1198
1199 private boolean leafOnly;
1200
1201 public boolean acceptNode(TreePath parent, N node, boolean leaf) {
1202 if (leafOnly && !leaf)
1203 return false;
1204 matcher.reset(getStringValue(node));
1205 return matcher.find();
1206 }
1207
1208 protected String getStringValue(N node) {
1209 return node.toString();
1210 }
1211 }
1212
1213
1214 private static Map<Object,Converter> createConvertersMap() {
1215 return new HashMap<Object,Converter>();
1216 }
1217 }