introduce treePathTraverser(tree)
[idea/community.git] / 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 }