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 }