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