platform/platform-api/src/com/intellij/util/ui/tree/TreeUtil.java

   1 /*
   2  * Copyright 2000-2017 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.util.ui.tree;
  17
  18 import com.intellij.ide.util.treeView.AbstractTreeBuilder;
  19 import com.intellij.openapi.application.Application;
  20 import com.intellij.openapi.application.ApplicationManager;
  21 import com.intellij.openapi.diagnostic.Logger;
  22 import com.intellij.openapi.project.Project;
  23 import com.intellij.openapi.util.ActionCallback;
  24 import com.intellij.openapi.util.Comparing;
  25 import com.intellij.openapi.wm.IdeFocusManager;
  26 import com.intellij.ui.ScrollingUtil;
  27 import com.intellij.ui.SimpleColoredComponent;
  28 import com.intellij.ui.awt.RelativePoint;
  29 import com.intellij.ui.treeStructure.Tree;
  30 import com.intellij.util.Range;
  31 import com.intellij.util.containers.JBIterable;
  32 import com.intellij.util.containers.JBTreeTraverser;
  33 import com.intellij.util.ui.UIUtil;
  34 import org.jetbrains.annotations.NonNls;
  35 import org.jetbrains.annotations.NotNull;
  36 import org.jetbrains.annotations.Nullable;
  37
  38 import javax.swing.*;
  39 import javax.swing.plaf.basic.BasicTreeUI;
  40 import javax.swing.tree.*;
  41 import java.awt.*;
  42 import java.awt.event.ActionEvent;
  43 import java.awt.event.KeyEvent;
  44 import java.util.*;
  45 import java.util.List;
  46
  47 import static com.intellij.openapi.wm.IdeFocusManager.getGlobalInstance;
  48
  49 public final class TreeUtil {
  50   private static final Logger LOG = Logger.getInstance("#com.intellij.util.ui.tree.TreeUtil");
  51   @NonNls @NotNull private static final String TREE_UTIL_SCROLL_TIME_STAMP = "TreeUtil.scrollTimeStamp";
  52
  53   private TreeUtil() {}
  54
  55   @NotNull
  56   public static JBTreeTraverser<TreePath> treePathTraverser(@NotNull JTree tree) {
  57     TreeModel model = tree.getModel();
  58     JBIterable<Integer> numbers = JBIterable.generate(0, i -> i + 1);
  59     Object root = model.getRoot();
  60     TreePath rootPath = root == null ? null : new TreePath(root);
  61     return new JBTreeTraverser<TreePath>(o -> {
  62       Object parent = o.getLastPathComponent();
  63       int count = model.getChildCount(parent);
  64
  65       return count == 0 ? JBIterable.empty() :
  66              numbers.take(count).map(
  67                index -> o.pathByAddingChild(model.getChild(parent, index)));
  68     })
  69       .withRoot(rootPath);
  70   }
  71
  72   @NotNull
  73   public static List<TreePath> collectExpandedPaths(@NotNull JTree tree){
  74     return treePathTraverser(tree).expandAndFilter(tree::isExpanded).toList();
  75   }
  76
  77   @NotNull
  78   public static <T> List<T> collectSelectedObjectsOfType(@NotNull JTree tree, @NotNull Class<T> clazz) {
  79     final TreePath[] selections = tree.getSelectionPaths();
  80     if (selections != null) {
  81       final ArrayList<T> result = new ArrayList<>();
  82       for (TreePath selection : selections) {
  83         final DefaultMutableTreeNode node = (DefaultMutableTreeNode)selection.getLastPathComponent();
  84         final Object userObject = node.getUserObject();
  85         if (clazz.isInstance(userObject)) {
  86           //noinspection unchecked
  87           result.add((T)userObject);
  88         }
  89       }
  90       return result;
  91     }
  92     return Collections.emptyList();
  93
  94   }
  95
  96   @NotNull
  97   public static List<TreePath> collectExpandedPaths(@NotNull JTree tree, @NotNull TreePath path) {
  98     return treePathTraverser(tree).expand(tree::isExpanded).withRoot(path).toList();
  99   }
 100
 101   /**
 102    * Expands specified paths.
 103    * @param tree JTree to apply expansion status to
 104    * @param paths to expand. See {@link #collectExpandedPaths(javax.swing.JTree, java.util.List)}
 105    */
 106   public static void restoreExpandedPaths(@NotNull final JTree tree, @NotNull final List<TreePath> paths){
 107     for(int i = paths.size() - 1; i >= 0; i--){
 108       tree.expandPath(paths.get(i));
 109     }
 110   }
 111
 112   @NotNull
 113   public static TreePath getPath(@NotNull TreeNode aRootNode, @NotNull TreeNode aNode) {
 114     TreeNode[] nodes = getPathFromRootTo(aRootNode, aNode, true);
 115     return new TreePath(nodes);
 116   }
 117
 118   public static boolean isAncestor(@NotNull TreeNode ancestor, @NotNull TreeNode node) {
 119     TreeNode parent = node;
 120     while (parent != null) {
 121       if (parent == ancestor) return true;
 122       parent = parent.getParent();
 123     }
 124     return false;
 125   }
 126
 127   private static boolean isAncestor(@NotNull final TreePath ancestor, @NotNull final TreePath path) {
 128     if (path.getPathCount() < ancestor.getPathCount()) return false;
 129     for (int i = 0; i < ancestor.getPathCount(); i++)
 130       if (!path.getPathComponent(i).equals(ancestor.getPathComponent(i))) return false;
 131     return true;
 132   }
 133
 134   private static boolean isDescendants(@NotNull final TreePath path, @NotNull final TreePath[] paths) {
 135     for (final TreePath ancestor : paths) {
 136       if (isAncestor(ancestor, path)) return true;
 137     }
 138     return false;
 139   }
 140
 141   @NotNull
 142   public static TreePath getPathFromRoot(@NotNull TreeNode node) {
 143     TreeNode[] path = getPathFromRootTo(null, node, false);
 144     return new TreePath(path);
 145   }
 146
 147   @NotNull
 148   private static TreeNode[] getPathFromRootTo(@Nullable TreeNode root, @NotNull TreeNode node, boolean includeRoot) {
 149     int height = 0;
 150     for (TreeNode n = node; n != root; n = n.getParent()) {
 151       height++;
 152     }
 153     TreeNode[] path = new TreeNode[includeRoot ? height+1 : height];
 154     int i = path.length-1;
 155     for (TreeNode n = node; i>=0; n = n.getParent()) {
 156       path[i--] = n;
 157     }
 158     return path;
 159   }
 160
 161   @Nullable
 162   public static TreeNode findNodeWithObject(final Object object, @NotNull final TreeModel model, final Object parent) {
 163     for (int i = 0; i < model.getChildCount(parent); i++) {
 164       final DefaultMutableTreeNode childNode = (DefaultMutableTreeNode) model.getChild(parent, i);
 165       if (childNode.getUserObject().equals(object)) return childNode;
 166     }
 167     return null;
 168   }
 169
 170   /**
 171    * Removes last component in the current selection path.
 172    * @param tree to remove selected node from.
 173    */
 174   public static void removeSelected(@NotNull final JTree tree) {
 175     TreePath[] paths = tree.getSelectionPaths();
 176     if (paths == null) {
 177       return;
 178     }
 179     for (TreePath path : paths) {
 180       removeLastPathComponent((DefaultTreeModel) tree.getModel(), path).restoreSelection(tree);
 181     }
 182   }
 183
 184   public static void removeLastPathComponent(@NotNull final JTree tree, @NotNull final TreePath pathToBeRemoved){
 185     removeLastPathComponent((DefaultTreeModel)tree.getModel(), pathToBeRemoved).restoreSelection(tree);
 186   }
 187
 188   @Nullable
 189   public static DefaultMutableTreeNode findNodeWithObject(@NotNull final DefaultMutableTreeNode aRoot, final Object aObject) {
 190     if (Comparing.equal(aRoot.getUserObject(), aObject)) {
 191       return aRoot;
 192     } else {
 193       for (int i = 0; i < aRoot.getChildCount(); i++) {
 194         final DefaultMutableTreeNode candidate = findNodeWithObject((DefaultMutableTreeNode) aRoot.getChildAt(i), aObject);
 195         if (null != candidate) {
 196           return candidate;
 197         }
 198       }
 199       return null;
 200     }
 201   }
 202
 203   @NotNull
 204   public static TreePath findCommonPath(@NotNull final TreePath[] treePaths) {
 205     LOG.assertTrue(areComponentsEqual(treePaths, 0));
 206     TreePath result = new TreePath(treePaths[0].getPathComponent(0));
 207     int pathIndex = 1;
 208     while (areComponentsEqual(treePaths, pathIndex)) {
 209       result = result.pathByAddingChild(treePaths[0].getPathComponent(pathIndex));
 210       pathIndex++;
 211     }
 212     return result;
 213   }
 214
 215   @NotNull
 216   public static ActionCallback selectFirstNode(@NotNull JTree tree) {
 217     TreePath selectionPath = getFirstNodePath(tree);
 218     return selectPath(tree, selectionPath);
 219   }
 220
 221   @NotNull
 222   public static TreePath getFirstNodePath(@NotNull JTree tree) {
 223     final TreeModel model = tree.getModel();
 224     final Object root = model.getRoot();
 225     TreePath selectionPath = new TreePath(root);
 226     if (!tree.isRootVisible() && model.getChildCount(root) > 0) {
 227       selectionPath = selectionPath.pathByAddingChild(model.getChild(root, 0));
 228     }
 229     return selectionPath;
 230   }
 231
 232   @NotNull
 233   public static TreePath getFirstLeafNodePath(@NotNull JTree tree) {
 234     final TreeModel model = tree.getModel();
 235     Object root = model.getRoot();
 236     TreePath selectionPath = new TreePath(root);
 237     while (model.getChildCount(root) > 0) {
 238       final Object child = model.getChild(root, 0);
 239       selectionPath = selectionPath.pathByAddingChild(child);
 240       root = child;
 241     }
 242     return selectionPath;
 243   }
 244
 245   @NotNull
 246   private static IndexTreePathState removeLastPathComponent(@NotNull final DefaultTreeModel model, @NotNull final TreePath pathToBeRemoved) {
 247     final IndexTreePathState selectionState = new IndexTreePathState(pathToBeRemoved);
 248     if (((MutableTreeNode) pathToBeRemoved.getLastPathComponent()).getParent() == null) return selectionState;
 249     model.removeNodeFromParent((MutableTreeNode)pathToBeRemoved.getLastPathComponent());
 250     return selectionState;
 251   }
 252
 253
 254   private static boolean areComponentsEqual(@NotNull final TreePath[] paths, final int componentIndex) {
 255     if (paths[0].getPathCount() <= componentIndex) return false;
 256     final Object pathComponent = paths[0].getPathComponent(componentIndex);
 257     for (final TreePath treePath : paths) {
 258       if (treePath.getPathCount() <= componentIndex) return false;
 259       if (!pathComponent.equals(treePath.getPathComponent(componentIndex))) return false;
 260     }
 261     return true;
 262   }
 263
 264   @NotNull
 265   private static TreePath[] removeDuplicates(@NotNull final TreePath[] paths) {
 266     final ArrayList<TreePath> result = new ArrayList<>();
 267     for (final TreePath path : paths) {
 268       if (!result.contains(path)) result.add(path);
 269     }
 270     return result.toArray(new TreePath[result.size()]);
 271   }
 272
 273   @NotNull
 274   public static TreePath[] selectMaximals(@Nullable final TreePath[] paths) {
 275     if (paths == null) return new TreePath[0];
 276     final TreePath[] noDuplicates = removeDuplicates(paths);
 277     final ArrayList<TreePath> result = new ArrayList<>();
 278     for (final TreePath path : noDuplicates) {
 279       final ArrayList<TreePath> otherPaths = new ArrayList<>(Arrays.asList(noDuplicates));
 280       otherPaths.remove(path);
 281       if (!isDescendants(path, otherPaths.toArray(new TreePath[otherPaths.size()]))) result.add(path);
 282     }
 283     return result.toArray(new TreePath[result.size()]);
 284   }
 285
 286   public static void sort(@NotNull final DefaultTreeModel model, @Nullable Comparator comparator) {
 287     sort((DefaultMutableTreeNode) model.getRoot(), comparator);
 288   }
 289
 290   public static void sort(@NotNull final DefaultMutableTreeNode node, @Nullable Comparator comparator) {
 291     sortRecursively(node, comparator);
 292   }
 293
 294   public static <T extends MutableTreeNode> void sortRecursively(@NotNull T node, @Nullable Comparator<? super T> comparator) {
 295     sortChildren(node, comparator);
 296     for (int i = 0; i < node.getChildCount(); i++) {
 297       //noinspection unchecked
 298       sortRecursively((T) node.getChildAt(i), comparator);
 299     }
 300   }
 301
 302   public static <T extends MutableTreeNode> void sortChildren(@NotNull T node, @Nullable Comparator<? super T> comparator) {
 303     //noinspection unchecked
 304     final List<T> children = (List)listChildren(node);
 305     Collections.sort(children, comparator);
 306     for (int i = node.getChildCount() - 1; i >= 0; i--) {
 307       node.remove(i);
 308     }
 309     addChildrenTo(node, children);
 310   }
 311
 312   public static void addChildrenTo(@NotNull final MutableTreeNode node, @NotNull final List<? extends TreeNode> children) {
 313     for (final Object aChildren : children) {
 314       final MutableTreeNode child = (MutableTreeNode)aChildren;
 315       node.insert(child, node.getChildCount());
 316     }
 317   }
 318
 319   public static boolean traverse(@NotNull final TreeNode node, @NotNull final Traverse traverse) {
 320     final int childCount = node.getChildCount();
 321     for (int i = 0; i < childCount; i++){
 322       if (!traverse(node.getChildAt(i), traverse)) return false;
 323     }
 324     return traverse.accept(node);
 325   }
 326
 327   public static boolean traverseDepth(@NotNull final TreeNode node, @NotNull final Traverse traverse) {
 328     if (!traverse.accept(node)) return false;
 329     final int childCount = node.getChildCount();
 330     for (int i = 0; i < childCount; i++)
 331       if (!traverseDepth(node.getChildAt(i), traverse)) return false;
 332     return true;
 333   }
 334
 335   @NotNull
 336   public static ActionCallback selectPath(@NotNull final JTree tree, final TreePath path) {
 337     return selectPath(tree, path, true);
 338   }
 339
 340   @NotNull
 341   public static ActionCallback selectPath(@NotNull final JTree tree, final TreePath path, boolean center) {
 342     tree.makeVisible(path);
 343     if (center) {
 344       return showRowCentred(tree, tree.getRowForPath(path));
 345     } else {
 346       final int row = tree.getRowForPath(path);
 347       return showAndSelect(tree, row - ScrollingUtil.ROW_PADDING, row + ScrollingUtil.ROW_PADDING, row, -1);
 348     }
 349   }
 350
 351   @NotNull
 352   public static ActionCallback moveDown(@NotNull final JTree tree) {
 353     final int size = tree.getRowCount();
 354     int row = tree.getLeadSelectionRow();
 355     if (row < size - 1) {
 356       row++;
 357       return showAndSelect(tree, row, row + 2, row, getSelectedRow(tree), false, true, true);
 358     } else {
 359       return ActionCallback.DONE;
 360     }
 361   }
 362
 363   @NotNull
 364   public static ActionCallback moveUp(@NotNull final JTree tree) {
 365     int row = tree.getLeadSelectionRow();
 366     if (row > 0) {
 367       row--;
 368       return showAndSelect(tree, row - 2, row, row, getSelectedRow(tree), false, true, true);
 369     } else {
 370       return ActionCallback.DONE;
 371     }
 372   }
 373
 374   @NotNull
 375   public static ActionCallback movePageUp(@NotNull final JTree tree) {
 376     final int visible = getVisibleRowCount(tree);
 377     if (visible <= 0){
 378       return moveHome(tree);
 379     }
 380     final int decrement = visible - 1;
 381     final int row = Math.max(getSelectedRow(tree) - decrement, 0);
 382     final int top = getFirstVisibleRow(tree) - decrement;
 383     final int bottom = top + visible - 1;
 384     return showAndSelect(tree, top, bottom, row, getSelectedRow(tree));
 385   }
 386
 387   @NotNull
 388   public static ActionCallback movePageDown(@NotNull final JTree tree) {
 389     final int visible = getVisibleRowCount(tree);
 390     if (visible <= 0){
 391       return moveEnd(tree);
 392     }
 393     final int size = tree.getRowCount();
 394     final int increment = visible - 1;
 395     final int index = Math.min(getSelectedRow(tree) + increment, size - 1);
 396     final int top = getFirstVisibleRow(tree) + increment;
 397     final int bottom = top + visible - 1;
 398     return showAndSelect(tree, top, bottom, index, getSelectedRow(tree));
 399   }
 400
 401   @NotNull
 402   private static ActionCallback moveHome(@NotNull final JTree tree) {
 403     return showRowCentred(tree, 0);
 404   }
 405
 406   @NotNull
 407   private static ActionCallback moveEnd(@NotNull final JTree tree) {
 408     return showRowCentred(tree, tree.getRowCount() - 1);
 409   }
 410
 411   @NotNull
 412   private static ActionCallback showRowCentred(@NotNull final JTree tree, final int row) {
 413     return showRowCentered(tree, row, true);
 414   }
 415
 416   @NotNull
 417   public static ActionCallback showRowCentered(@NotNull final JTree tree, final int row, final boolean centerHorizontally) {
 418     return showRowCentered(tree, row, centerHorizontally, true);
 419   }
 420
 421   @NotNull
 422   public static ActionCallback showRowCentered(@NotNull final JTree tree, final int row, final boolean centerHorizontally, boolean scroll) {
 423     final int visible = getVisibleRowCount(tree);
 424
 425     final int top = visible > 0 ? row - (visible - 1)/ 2 : row;
 426     final int bottom = visible > 0 ? top + visible - 1 : row;
 427     return showAndSelect(tree, top, bottom, row, -1, false, scroll, false);
 428   }
 429
 430   @NotNull
 431   public static ActionCallback showAndSelect(@NotNull final JTree tree, int top, int bottom, final int row, final int previous) {
 432     return showAndSelect(tree, top, bottom, row, previous, false);
 433   }
 434
 435   @NotNull
 436   public static ActionCallback showAndSelect(@NotNull final JTree tree, int top, int bottom, final int row, final int previous, boolean addToSelection) {
 437     return showAndSelect(tree, top, bottom, row, previous, addToSelection, true, false);
 438   }
 439
 440   @NotNull
 441   public static ActionCallback showAndSelect(@NotNull final JTree tree, int top, int bottom, final int row, final int previous, final boolean addToSelection, final boolean scroll) {
 442     return showAndSelect(tree, top, bottom, row, previous, addToSelection, scroll, false);
 443   }
 444
 445   @NotNull
 446   public static ActionCallback showAndSelect(@NotNull final JTree tree, int top, int bottom, final int row, final int previous, final boolean addToSelection, final boolean scroll, final boolean resetSelection) {
 447     final TreePath path = tree.getPathForRow(row);
 448
 449     if (path == null) return ActionCallback.DONE;
 450
 451     final int size = tree.getRowCount();
 452     if (size == 0) {
 453       tree.clearSelection();
 454       return ActionCallback.DONE;
 455     }
 456     if (top < 0){
 457       top = 0;
 458     }
 459     if (bottom >= size){
 460       bottom = size - 1;
 461     }
 462
 463     if (row >= tree.getRowCount()) return ActionCallback.DONE;
 464
 465     boolean okToScroll = true;
 466     if (tree.isShowing()) {
 467       if (!tree.isValid()) {
 468         tree.validate();
 469       }
 470     } else {
 471       Application app = ApplicationManager.getApplication();
 472       if (app != null && app.isUnitTestMode()) {
 473         okToScroll = false;
 474       }
 475     }
 476
 477     Runnable selectRunnable = () -> {
 478       if (!tree.isRowSelected(row)) {
 479         if (addToSelection) {
 480           tree.getSelectionModel().addSelectionPath(tree.getPathForRow(row));
 481         } else {
 482           tree.setSelectionRow(row);
 483         }
 484       } else if (resetSelection) {
 485         if (!addToSelection) {
 486           tree.setSelectionRow(row);
 487         }
 488       }
 489     };
 490
 491
 492     if (!okToScroll || !scroll) {
 493       selectRunnable.run();
 494       return ActionCallback.DONE;
 495     }
 496
 497
 498     final Rectangle rowBounds = tree.getRowBounds(row);
 499     if (rowBounds == null) return ActionCallback.DONE;
 500
 501     Rectangle topBounds = tree.getRowBounds(top);
 502     if (topBounds == null) {
 503       topBounds = rowBounds;
 504     }
 505
 506     Rectangle bottomBounds = tree.getRowBounds(bottom);
 507     if (bottomBounds == null) {
 508       bottomBounds = rowBounds;
 509     }
 510
 511     Rectangle bounds = topBounds.union(bottomBounds);
 512     bounds.x = rowBounds.x;
 513     bounds.width = rowBounds.width;
 514
 515     final Rectangle visible = tree.getVisibleRect();
 516     if (visible.contains(bounds)) {
 517       selectRunnable.run();
 518       return ActionCallback.DONE;
 519     } else {
 520       final Component comp =
 521         tree.getCellRenderer().getTreeCellRendererComponent(tree, path.getLastPathComponent(), true, true, false, row, false);
 522
 523       if (comp instanceof SimpleColoredComponent) {
 524         final SimpleColoredComponent renderer = (SimpleColoredComponent)comp;
 525         final Dimension scrollableSize = renderer.computePreferredSize(true);
 526         bounds.width = scrollableSize.width;
 527       }
 528     }
 529
 530     final ActionCallback callback = new ActionCallback();
 531
 532
 533     selectRunnable.run();
 534
 535       final Range<Integer> range = getExpandControlRange(tree, path);
 536       if (range != null) {
 537         int delta = bounds.x - range.getFrom().intValue();
 538         bounds.x -= delta;
 539         bounds.width -= delta;
 540       }
 541
 542       if (visible.width < bounds.width) {
 543         bounds.width = visible.width;
 544       }
 545
 546       if (tree instanceof Tree && !((Tree)tree).isHorizontalAutoScrollingEnabled()) {
 547         bounds.x = 0;
 548       }
 549
 550     LOG.debug("tree scroll: ", path);
 551     tree.scrollRectToVisible(bounds);
 552     // try to scroll later when the tree is ready
 553     Object property = tree.getClientProperty(TREE_UTIL_SCROLL_TIME_STAMP);
 554     long stamp = property instanceof Long ? (Long)property + 1L : Long.MIN_VALUE;
 555     tree.putClientProperty(TREE_UTIL_SCROLL_TIME_STAMP, stamp);
 556     // store relative offset because the row can be moved during the tree updating
 557     int offset = rowBounds.y - bounds.y;
 558
 559     AbstractTreeBuilder builder = AbstractTreeBuilder.getBuilderFor(tree);
 560     scrollToVisible(tree, path, bounds, offset, stamp, callback::setDone, builder, 3);
 561
 562     return callback;
 563   }
 564
 565   private static void scrollToVisible(JTree tree, TreePath path, Rectangle bounds, int offset, long expected, Runnable done,
 566                                       AbstractTreeBuilder builder, int attempt) {
 567     Runnable scroll = () -> {
 568       Rectangle pathBounds = attempt <= 0 ? null : tree.getPathBounds(path);
 569       if (pathBounds != null) {
 570         Object property = tree.getClientProperty(TREE_UTIL_SCROLL_TIME_STAMP);
 571         long stamp = property instanceof Long ? (Long)property : Long.MAX_VALUE;
 572         LOG.debug("tree scroll ", attempt, stamp == expected ? ": try again: " : ": ignore: ", path);
 573         if (stamp == expected) {
 574           bounds.y = pathBounds.y - offset; // restore bounds according to the current row
 575           Rectangle visible = tree.getVisibleRect();
 576           if (bounds.y < visible.y || bounds.y > visible.y + Math.max(0, visible.height - bounds.height)) {
 577             tree.scrollRectToVisible(bounds);
 578             scrollToVisible(tree, path, bounds, offset, expected, done, builder, attempt - 1);
 579             return; // try to scroll again
 580           }
 581         }
 582       }
 583       done.run();
 584     };
 585     //noinspection SSBasedInspection
 586     SwingUtilities.invokeLater(builder == null ? scroll : () -> builder.getReady(TreeUtil.class).doWhenDone(scroll));
 587   }
 588
 589   // this method returns FIRST selected row but not LEAD
 590   private static int getSelectedRow(@NotNull final JTree tree) {
 591     return tree.getRowForPath(tree.getSelectionPath());
 592   }
 593
 594   private static int getFirstVisibleRow(@NotNull final JTree tree) {
 595     final Rectangle visible = tree.getVisibleRect();
 596     int row = -1;
 597     for (int i=0; i < tree.getRowCount(); i++) {
 598       final Rectangle bounds = tree.getRowBounds(i);
 599       if (visible.y <= bounds.y && visible.y + visible.height >= bounds.y + bounds.height) {
 600         row = i;
 601         break;
 602       }
 603     }
 604     return row;
 605   }
 606
 607   public static int getVisibleRowCount(@NotNull final JTree tree) {
 608     final Rectangle visible = tree.getVisibleRect();
 609
 610     if (visible == null) return 0;
 611
 612     int count = 0;
 613     for (int i=0; i < tree.getRowCount(); i++) {
 614       final Rectangle bounds = tree.getRowBounds(i);
 615       if (bounds == null) continue;
 616       if (visible.y <= bounds.y && visible.y + visible.height >= bounds.y + bounds.height) {
 617         count++;
 618       }
 619     }
 620     return count;
 621   }
 622
 623   /**
 624    * works correctly for trees with fixed row height only.
 625    * For variable height trees (e.g. trees with custom tree node renderer) use the {@link #getVisibleRowCount(JTree)} which is slower
 626    */
 627   public static int getVisibleRowCountForFixedRowHeight(@NotNull final JTree tree) {
 628     // myTree.getVisibleRowCount returns 20
 629     Rectangle bounds = tree.getRowBounds(0);
 630     int rowHeight = bounds == null ? 0 : bounds.height;
 631     return rowHeight == 0 ? tree.getVisibleRowCount() : tree.getVisibleRect().height / rowHeight;
 632   }
 633
 634   @SuppressWarnings({"HardCodedStringLiteral"})
 635   public static void installActions(@NotNull final JTree tree) {
 636     tree.getActionMap().put("scrollUpChangeSelection", new AbstractAction() {
 637       @Override
 638       public void actionPerformed(final ActionEvent e) {
 639         movePageUp(tree);
 640       }
 641     });
 642     tree.getActionMap().put("scrollDownChangeSelection", new AbstractAction() {
 643       @Override
 644       public void actionPerformed(final ActionEvent e) {
 645         movePageDown(tree);
 646       }
 647     });
 648     tree.getActionMap().put("selectPrevious", new AbstractAction() {
 649       @Override
 650       public void actionPerformed(final ActionEvent e) {
 651         moveUp(tree);
 652       }
 653     });
 654     tree.getActionMap().put("selectNext", new AbstractAction() {
 655       @Override
 656       public void actionPerformed(final ActionEvent e) {
 657         moveDown(tree);
 658       }
 659     });
 660     copyAction(tree, "selectLast", "selectLastChangeLead");
 661     copyAction(tree, "selectFirst", "selectFirstChangeLead");
 662
 663     InputMap inputMap = tree.getInputMap(JComponent.WHEN_FOCUSED);
 664     UIUtil.maybeInstall(inputMap, "scrollUpChangeSelection", KeyStroke.getKeyStroke(KeyEvent.VK_PAGE_UP, 0));
 665     UIUtil.maybeInstall(inputMap, "scrollDownChangeSelection", KeyStroke.getKeyStroke(KeyEvent.VK_PAGE_DOWN, 0));
 666     UIUtil.maybeInstall(inputMap, "selectNext", KeyStroke.getKeyStroke(KeyEvent.VK_DOWN, 0));
 667     UIUtil.maybeInstall(inputMap, "selectPrevious", KeyStroke.getKeyStroke(KeyEvent.VK_UP, 0));
 668     UIUtil.maybeInstall(inputMap, "selectLast", KeyStroke.getKeyStroke(KeyEvent.VK_END, 0));
 669     UIUtil.maybeInstall(inputMap, "selectFirst", KeyStroke.getKeyStroke(KeyEvent.VK_HOME, 0));
 670   }
 671
 672   private static void copyAction(@NotNull final JTree tree, String original, String copyTo) {
 673     final Action action = tree.getActionMap().get(original);
 674     if (action != null) {
 675       tree.getActionMap().put(copyTo, action);
 676     }
 677   }
 678
 679   public static void collapseAll(@NotNull JTree tree, final int keepSelectionLevel) {
 680     final TreePath leadSelectionPath = tree.getLeadSelectionPath();
 681     // Collapse all
 682     int row = tree.getRowCount() - 1;
 683     while (row >= 0) {
 684       tree.collapseRow(row);
 685       row--;
 686     }
 687     Object root = tree.getModel().getRoot();
 688     if (root != null) {
 689       tree.expandPath(new TreePath(root));
 690     }
 691     if (leadSelectionPath != null) {
 692       final Object[] path = leadSelectionPath.getPath();
 693       final Object[] pathToSelect = new Object[path.length > keepSelectionLevel && keepSelectionLevel >= 0 ? keepSelectionLevel : path.length];
 694       System.arraycopy(path, 0, pathToSelect, 0, pathToSelect.length);
 695       if (pathToSelect.length == 0) return;
 696       selectPath(tree, new TreePath(pathToSelect));
 697     }
 698   }
 699
 700   public static void selectNode(@NotNull final JTree tree, final TreeNode node) {
 701     selectPath(tree, getPathFromRoot(node));
 702   }
 703
 704   public static void moveSelectedRow(@NotNull final JTree tree, final int direction){
 705     final TreePath selectionPath = tree.getSelectionPath();
 706     final DefaultMutableTreeNode treeNode = (DefaultMutableTreeNode)selectionPath.getLastPathComponent();
 707     final DefaultMutableTreeNode parent = (DefaultMutableTreeNode)treeNode.getParent();
 708     final int idx = parent.getIndex(treeNode);
 709     ((DefaultTreeModel)tree.getModel()).removeNodeFromParent(treeNode);
 710     ((DefaultTreeModel)tree.getModel()).insertNodeInto(treeNode, parent, idx + direction);
 711     selectNode(tree, treeNode);
 712   }
 713
 714   /**
 715    * @deprecated use {@link #listChildren(TreeNode)} instead
 716    */
 717   @NotNull
 718   public static ArrayList<TreeNode> childrenToArray(@NotNull TreeNode node) {
 719     return (ArrayList<TreeNode>)listChildren(node);
 720   }
 721
 722   @NotNull
 723   public static List<TreeNode> listChildren(@NotNull final TreeNode node) {
 724     //ApplicationManager.getApplication().assertIsDispatchThread();
 725     int size = node.getChildCount();
 726     ArrayList<TreeNode> result = new ArrayList<>(size);
 727     for(int i = 0; i < size; i++){
 728       TreeNode child = node.getChildAt(i);
 729       LOG.assertTrue(child != null);
 730       result.add(child);
 731     }
 732     return result;
 733   }
 734
 735   public static void expandRootChildIfOnlyOne(@Nullable final JTree tree) {
 736     if (tree == null) return;
 737     final Runnable runnable = () -> {
 738       final DefaultMutableTreeNode root = (DefaultMutableTreeNode)tree.getModel().getRoot();
 739       tree.expandPath(new TreePath(new Object[]{root}));
 740       if (root.getChildCount() == 1) {
 741         TreeNode firstChild = root.getFirstChild();
 742         tree.expandPath(new TreePath(new Object[]{root, firstChild}));
 743       }
 744     };
 745     UIUtil.invokeLaterIfNeeded(runnable);
 746   }
 747
 748   public static void expandAll(@NotNull final JTree tree) {
 749     tree.expandPath(new TreePath(tree.getModel().getRoot()));
 750     int oldRowCount = 0;
 751     do {
 752       int rowCount = tree.getRowCount();
 753       if (rowCount == oldRowCount) break;
 754       oldRowCount = rowCount;
 755       for (int i = 0; i < rowCount; i++) {
 756           tree.expandRow(i);
 757         }
 758      }
 759     while (true);
 760   }
 761
 762   /**
 763    * Expands n levels of the tree counting from the root
 764    * @param tree to expand nodes of
 765    * @param levels depths of the expantion
 766    */
 767   public static void expand(@NotNull JTree tree, int levels) {
 768     expand(tree, new TreePath(tree.getModel().getRoot()), levels);
 769   }
 770
 771   /**
 772    * Expands n levels of the tree counting from the root and return true if there is no nodes to expand
 773    * @param tree to expand nodes of
 774    * @param levels depths of the expantion
 775    */
 776   public static boolean expandWithResult(@NotNull JTree tree, int levels) {
 777     return expand(tree, new TreePath(tree.getModel().getRoot()), levels);
 778   }
 779
 780   private static boolean expand(@NotNull JTree tree, @NotNull TreePath path, int levels) {
 781     if (levels == 0) return false;
 782     tree.expandPath(path);
 783     TreeNode node = (TreeNode)path.getLastPathComponent();
 784     Enumeration children = node.children();
 785
 786     boolean isReady = true;
 787     while (children.hasMoreElements()) {
 788       if (!expand(tree, path.pathByAddingChild(children.nextElement()) , levels - 1))
 789         isReady = false;
 790     }
 791     return isReady;
 792   }
 793
 794   @NotNull
 795   public static ActionCallback selectInTree(DefaultMutableTreeNode node, boolean requestFocus, @NotNull JTree tree) {
 796     return selectInTree(node, requestFocus, tree, true);
 797   }
 798
 799   @NotNull
 800   public static ActionCallback selectInTree(@Nullable DefaultMutableTreeNode node, boolean requestFocus, @NotNull JTree tree, boolean center) {
 801     if (node == null) return ActionCallback.DONE;
 802
 803     final TreePath treePath = new TreePath(node.getPath());
 804     tree.expandPath(treePath);
 805     if (requestFocus) {
 806       getGlobalInstance().doWhenFocusSettlesDown(() -> {
 807         getGlobalInstance().requestFocus(tree, true);
 808       });
 809     }
 810     return selectPath(tree, treePath, center);
 811   }
 812
 813   @NotNull
 814   public static ActionCallback selectInTree(Project project, @Nullable DefaultMutableTreeNode node, boolean requestFocus, @NotNull JTree tree, boolean center) {
 815     if (node == null) return ActionCallback.DONE;
 816
 817     final TreePath treePath = new TreePath(node.getPath());
 818     tree.expandPath(treePath);
 819     if (requestFocus) {
 820       ActionCallback result = new ActionCallback(2);
 821       IdeFocusManager.getInstance(project).requestFocus(tree, true).notifyWhenDone(result);
 822       selectPath(tree, treePath, center).notifyWhenDone(result);
 823       return result;
 824     }
 825     return selectPath(tree, treePath, center);
 826   }
 827
 828   @NotNull
 829   public static List<TreePath> collectSelectedPaths(@NotNull final JTree tree, @NotNull final TreePath treePath) {
 830     final ArrayList<TreePath> result = new ArrayList<>();
 831     final TreePath[] selections = tree.getSelectionPaths();
 832     if (selections != null) {
 833       for (TreePath selection : selections) {
 834         if (treePath.isDescendant(selection)) {
 835           result.add(selection);
 836         }
 837       }
 838     }
 839     return result;
 840   }
 841
 842   public static void unselectPath(@NotNull JTree tree, @Nullable TreePath path) {
 843     if (path == null) return;
 844     TreePath[] selectionPaths = tree.getSelectionPaths();
 845     if (selectionPaths == null) return;
 846
 847     for (TreePath selectionPath : selectionPaths) {
 848       if (selectionPath.getPathCount() > path.getPathCount() && path.isDescendant(selectionPath)) {
 849         tree.removeSelectionPath(selectionPath);
 850       }
 851     }
 852   }
 853
 854   @Nullable
 855   public static Range<Integer> getExpandControlRange(@NotNull final JTree aTree, @Nullable final TreePath path) {
 856     TreeModel treeModel = aTree.getModel();
 857
 858     final BasicTreeUI basicTreeUI = (BasicTreeUI)aTree.getUI();
 859     Icon expandedIcon = basicTreeUI.getExpandedIcon();
 860
 861
 862     Range<Integer> box = null;
 863     if (path != null && !treeModel.isLeaf(path.getLastPathComponent())) {
 864       int boxWidth;
 865       Insets i = aTree.getInsets();
 866
 867       if (expandedIcon != null) {
 868         boxWidth = expandedIcon.getIconWidth();
 869       }
 870       else {
 871         boxWidth = 8;
 872       }
 873
 874       int boxLeftX = i != null ? i.left : 0;
 875
 876       boolean leftToRight = aTree.getComponentOrientation().isLeftToRight();
 877       int depthOffset = getDepthOffset(aTree);
 878       int totalChildIndent = basicTreeUI.getLeftChildIndent() + basicTreeUI.getRightChildIndent();
 879
 880       if (leftToRight) {
 881         boxLeftX += (path.getPathCount() + depthOffset - 2) * totalChildIndent + basicTreeUI.getLeftChildIndent() -
 882             boxWidth / 2;
 883       }
 884       int boxRightX = boxLeftX + boxWidth;
 885
 886       box = new Range<>(boxLeftX, boxRightX);
 887     }
 888     return box;
 889   }
 890
 891   public static int getDepthOffset(@NotNull JTree aTree) {
 892     if (aTree.isRootVisible()) {
 893       return aTree.getShowsRootHandles() ? 1 : 0;
 894     }
 895     else {
 896       return aTree.getShowsRootHandles() ? 0 : -1;
 897     }
 898   }
 899
 900   @NotNull
 901   public static RelativePoint getPointForSelection(@NotNull JTree aTree) {
 902     final int[] rows = aTree.getSelectionRows();
 903     if (rows == null || rows.length == 0) {
 904       return RelativePoint.getCenterOf(aTree);
 905     }
 906     return getPointForRow(aTree, rows[rows.length - 1]);
 907   }
 908
 909   @NotNull
 910   public static RelativePoint getPointForRow(@NotNull JTree aTree, int aRow) {
 911     return getPointForPath(aTree, aTree.getPathForRow(aRow));
 912   }
 913
 914   @NotNull
 915   public static RelativePoint getPointForPath(@NotNull JTree aTree, TreePath path) {
 916     final Rectangle rowBounds = aTree.getPathBounds(path);
 917     rowBounds.x += 20;
 918     return getPointForBounds(aTree, rowBounds);
 919   }
 920
 921   @NotNull
 922   public static RelativePoint getPointForBounds(JComponent aComponent, @NotNull final Rectangle aBounds) {
 923     return new RelativePoint(aComponent, new Point(aBounds.x, (int)aBounds.getMaxY()));
 924   }
 925
 926   public static boolean isOverSelection(@NotNull final JTree tree, @NotNull final Point point) {
 927     TreePath path = tree.getPathForLocation(point.x, point.y);
 928     return path != null && tree.getSelectionModel().isPathSelected(path);
 929   }
 930
 931   public static void dropSelectionButUnderPoint(@NotNull JTree tree, @NotNull Point treePoint) {
 932     final TreePath toRetain = tree.getPathForLocation(treePoint.x, treePoint.y);
 933     if (toRetain == null) return;
 934
 935     TreePath[] selection = tree.getSelectionModel().getSelectionPaths();
 936     selection = selection == null ? new TreePath[0] : selection;
 937     for (TreePath each : selection) {
 938       if (toRetain.equals(each)) continue;
 939       tree.getSelectionModel().removeSelectionPath(each);
 940     }
 941   }
 942
 943   @Nullable
 944   public static Object getUserObject(@Nullable Object node) {
 945     return node instanceof DefaultMutableTreeNode ? ((DefaultMutableTreeNode)node).getUserObject() : node;
 946   }
 947
 948   @Nullable
 949   public static TreePath getSelectedPathIfOne(JTree tree) {
 950     TreePath[] paths = tree.getSelectionPaths();
 951     return paths != null && paths.length == 1 ? paths[0] : null;
 952   }
 953
 954   @FunctionalInterface
 955   public interface Traverse{
 956     boolean accept(Object node);
 957   }
 958
 959   public static void ensureSelection(@NotNull JTree tree) {
 960     final TreePath[] paths = tree.getSelectionPaths();
 961
 962     if (paths != null) {
 963       for (TreePath each : paths) {
 964         if (tree.getRowForPath(each) >= 0 && tree.isVisible(each)) {
 965           return;
 966         }
 967       }
 968     }
 969
 970     for (int eachRow = 0; eachRow < tree.getRowCount(); eachRow++) {
 971       TreePath eachPath = tree.getPathForRow(eachRow);
 972       if (eachPath != null && tree.isVisible(eachPath)) {
 973         tree.setSelectionPath(eachPath);
 974         break;
 975       }
 976     }
 977   }
 978
 979   public static <T extends MutableTreeNode> void insertNode(@NotNull T child, @NotNull T parent, @Nullable DefaultTreeModel model,
 980                                                             @NotNull Comparator<? super T> comparator) {
 981     int index = indexedBinarySearch(parent, child, comparator);
 982     if (index >= 0) {
 983       LOG.error("Node " + child + " is already added to " + parent);
 984       return;
 985     }
 986     int insertionPoint = -(index + 1);
 987     if (model != null) {
 988       model.insertNodeInto(child, parent, insertionPoint);
 989     }
 990     else {
 991       parent.insert(child, insertionPoint);
 992     }
 993   }
 994
 995   public static <T extends TreeNode> int indexedBinarySearch(@NotNull T parent, @NotNull T key, @NotNull Comparator<? super T> comparator) {
 996     int low = 0;
 997     int high = parent.getChildCount() - 1;
 998
 999     while (low <= high) {
1000       int mid = (low + high) / 2;
1001       //noinspection unchecked
1002       T treeNode = (T)parent.getChildAt(mid);
1003       int cmp = comparator.compare(treeNode, key);
1004       if (cmp < 0) {
1005         low = mid + 1;
1006       }
1007       else if (cmp > 0) {
1008         high = mid - 1;
1009       }
1010       else {
1011         return mid; // key found
1012       }
1013     }
1014     return -(low + 1);  // key not found
1015   }
1016
1017   @NotNull
1018   public static Comparator<TreePath> getDisplayOrderComparator(@NotNull final JTree tree) {
1019     return Comparator.comparingInt(tree::getRowForPath);
1020   }
1021 }