/*

 * Copyright 1997-2008 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

package javax.swing;

import java.awt.*;

import java.awt.event.*;

import java.beans.*;

import java.io.*;

import java.util.*;

import javax.swing.event.*;

import javax.swing.plaf.*;

import javax.swing.tree.*;

import javax.swing.text.Position;

import javax.accessibility.*;

import sun.swing.SwingUtilities2;

import sun.swing.SwingUtilities2.Section;

import static sun.swing.SwingUtilities2.Section.*;

/**

 * <a name="jtree_description">

 * A control that displays a set of hierarchical data as an outline.

 * You can find task-oriented documentation and examples of using trees in

 * <a href="http://java.sun.com/docs/books/tutorial/uiswing/components/tree.html">How to Use Trees</a>,

 * a section in <em>The Java Tutorial.</em>

 * <p>

 * A specific node in a tree can be identified either by a

 * <code>TreePath</code> (an object

 * that encapsulates a node and all of its ancestors), or by its

 * display row, where each row in the display area displays one node.

 * An <i>expanded</i> node is a non-leaf node (as identified by

 * <code>TreeModel.isLeaf(node)</code> returning false) that will displays

 * its children when all its ancestors are <i>expanded</i>.

 * A <i>collapsed</i>

 * node is one which hides them. A <i>hidden</i> node is one which is

 * under a collapsed ancestor. All of a <i>viewable</i> nodes parents

 * are expanded, but may or may not be displayed. A <i>displayed</i> node

 * is both viewable and in the display area, where it can be seen.

 * <p>

 * The following <code>JTree</code> methods use "visible" to mean "displayed":

 * <ul>

 * <li><code>isRootVisible()</code>

 * <li><code>setRootVisible()</code>

 * <li><code>scrollPathToVisible()</code>

 * <li><code>scrollRowToVisible()</code>

 * <li><code>getVisibleRowCount()</code>

 * <li><code>setVisibleRowCount()</code>

 * </ul>

 * <p>

 * The next group of <code>JTree</code> methods use "visible" to mean

 * "viewable" (under an expanded parent):

 * <ul>

 * <li><code>isVisible()</code>

 * <li><code>makeVisible()</code>

 * </ul>

 * <p>

 * If you are interested in knowing when the selection changes implement

 * the <code>TreeSelectionListener</code> interface and add the instance

 * using the method <code>addTreeSelectionListener</code>.

 * <code>valueChanged</code> will be invoked when the

 * selection changes, that is if the user clicks twice on the same

 * node <code>valueChanged</code> will only be invoked once.

 * <p>

 * If you are interested in detecting either double-click events or when

 * a user clicks on a node, regardless of whether or not it was selected,

 * we recommend you do the following:

 * <pre>

 * final JTree tree = ...;

 *

 * MouseListener ml = new MouseAdapter() {

 *     public void <b>mousePressed</b>(MouseEvent e) {

 *         int selRow = tree.getRowForLocation(e.getX(), e.getY());

 *         TreePath selPath = tree.getPathForLocation(e.getX(), e.getY());

 *         if(selRow != -1) {

 *             if(e.getClickCount() == 1) {

 *                 mySingleClick(selRow, selPath);

 *             }

 *             else if(e.getClickCount() == 2) {

 *                 myDoubleClick(selRow, selPath);

 *             }

 *         }

 *     }

 * };

 * tree.addMouseListener(ml);

 * </pre>

 * NOTE: This example obtains both the path and row, but you only need to

 * get the one you're interested in.

 * <p>

 * To use <code>JTree</code> to display compound nodes

 * (for example, nodes containing both

 * a graphic icon and text), subclass {@link TreeCellRenderer} and use

 * {@link #setCellRenderer} to tell the tree to use it. To edit such nodes,

 * subclass {@link TreeCellEditor} and use {@link #setCellEditor}.

 * <p>

 * Like all <code>JComponent</code> classes, you can use {@link InputMap} and

 * {@link ActionMap}

 * to associate an {@link Action} object with a {@link KeyStroke}

 * and execute the action under specified conditions.

 * <p>

 * <strong>Warning:</strong> Swing is not thread safe. For more

 * information see <a

 * href="package-summary.html#threading">Swing's Threading

 * Policy</a>.

 * <p>

 * <strong>Warning:</strong>

 * Serialized objects of this class will not be compatible with

 * future Swing releases. The current serialization support is

 * appropriate for short term storage or RMI between applications running

 * the same version of Swing.  As of 1.4, support for long term storage

 * of all JavaBeans<sup><font size="-2">TM</font></sup>

 * has been added to the <code>java.beans</code> package.

 * Please see {@link java.beans.XMLEncoder}.

 *

 * @beaninfo

 *   attribute: isContainer false

 * description: A component that displays a set of hierarchical data as an outline.

 *

 * @author Rob Davis

 * @author Ray Ryan

 * @author Scott Violet

 */

public class JTree extends JComponent implements Scrollable, Accessible

{

    /**

     * @see #getUIClassID

     * @see #readObject

     */

    private static final String uiClassID = "TreeUI";

    /**

     * The model that defines the tree displayed by this object.

     */

    transient protected TreeModel        treeModel;

    /**

     * Models the set of selected nodes in this tree.

     */

    transient protected TreeSelectionModel selectionModel;

    /**

     * True if the root node is displayed, false if its children are

     * the highest visible nodes.

     */

    protected boolean                    rootVisible;

    /**

     * The cell used to draw nodes. If <code>null</code>, the UI uses a default

     * <code>cellRenderer</code>.

     */

    transient protected TreeCellRenderer  cellRenderer;

    /**

     * Height to use for each display row. If this is <= 0 the renderer

     * determines the height for each row.

     */

    protected int                         rowHeight;

    private boolean                       rowHeightSet = false;

    /**

     * Maps from <code>TreePath</code> to <code>Boolean</code>

     * indicating whether or not the

     * particular path is expanded. This ONLY indicates whether a

     * given path is expanded, and NOT if it is visible or not. That

     * information must be determined by visiting all the parent

     * paths and seeing if they are visible.

     */

    transient private Hashtable<TreePath, Boolean> expandedState;

    /**

     * True if handles are displayed at the topmost level of the tree.

     * <p>

     * A handle is a small icon that displays adjacent to the node which

     * allows the user to click once to expand or collapse the node. A

     * common interface shows a plus sign (+) for a node which can be

     * expanded and a minus sign (-) for a node which can be collapsed.

     * Handles are always shown for nodes below the topmost level.

     * <p>

     * If the <code>rootVisible</code> setting specifies that the root

     * node is to be displayed, then that is the only node at the topmost

     * level. If the root node is not displayed, then all of its

     * children are at the topmost level of the tree. Handles are

     * always displayed for nodes other than the topmost.

     * <p>

     * If the root node isn't visible, it is generally a good to make

     * this value true. Otherwise, the tree looks exactly like a list,

     * and users may not know that the "list entries" are actually

     * tree nodes.

     *

     * @see #rootVisible

     */

    protected boolean           showsRootHandles;

    private boolean             showsRootHandlesSet = false;

    /**

     * Creates a new event and passed it off the

     * <code>selectionListeners</code>.

     */

    protected transient TreeSelectionRedirector selectionRedirector;

    /**

     * Editor for the entries.  Default is <code>null</code>

     * (tree is not editable).

     */

    transient protected TreeCellEditor          cellEditor;

    /**

     * Is the tree editable? Default is false.

     */

    protected boolean                 editable;

    /**

     * Is this tree a large model? This is a code-optimization setting.

     * A large model can be used when the cell height is the same for all

     * nodes. The UI will then cache very little information and instead

     * continually message the model. Without a large model the UI caches

     * most of the information, resulting in fewer method calls to the model.

     * <p>

     * This value is only a suggestion to the UI. Not all UIs will

     * take advantage of it. Default value is false.

     */

    protected boolean                 largeModel;

    /**

     * Number of rows to make visible at one time. This value is used for

     * the <code>Scrollable</code> interface. It determines the preferred

     * size of the display area.

     */

    protected int                     visibleRowCount;

    /**

     * If true, when editing is to be stopped by way of selection changing,

     * data in tree changing or other means <code>stopCellEditing</code>

     * is invoked, and changes are saved. If false,

     * <code>cancelCellEditing</code> is invoked, and changes

     * are discarded. Default is false.

     */

    protected boolean                 invokesStopCellEditing;

    /**

     * If true, when a node is expanded, as many of the descendants are

     * scrolled to be visible.

     */

    protected boolean                 scrollsOnExpand;

    private boolean                   scrollsOnExpandSet = false;

    /**

     * Number of mouse clicks before a node is expanded.

     */

    protected int                     toggleClickCount;

    /**

     * Updates the <code>expandedState</code>.

     */

    transient protected TreeModelListener       treeModelListener;

    /**

     * Used when <code>setExpandedState</code> is invoked,

     * will be a <code>Stack</code> of <code>Stack</code>s.

     */

    transient private Stack<Stack<TreePath>> expandedStack;

    /**

     * Lead selection path, may not be <code>null</code>.

     */

    private TreePath                  leadPath;

    /**

     * Anchor path.

     */

    private TreePath                  anchorPath;

    /**

     * True if paths in the selection should be expanded.

     */

    private boolean                   expandsSelectedPaths;

    /**

     * This is set to true for the life of the <code>setUI</code> call.

     */

    private boolean                   settingUI;

    /** If true, mouse presses on selections initiate a drag operation. */

    private boolean dragEnabled;

    /**

     * The drop mode for this component.

     */

    private DropMode dropMode = DropMode.USE_SELECTION;

    /**

     * The drop location.

     */

    private transient DropLocation dropLocation;

    /**

     * A subclass of <code>TransferHandler.DropLocation</code> representing

     * a drop location for a <code>JTree</code>.

     *

     * @see #getDropLocation

     * @since 1.6

     */

    public static final class DropLocation extends TransferHandler.DropLocation {

        private final TreePath path;

        private final int index;

        private DropLocation(Point p, TreePath path, int index) {

            super(p);

            this.path = path;

            this.index = index;

        }

        /**

         * Returns the index where the dropped data should be inserted

         * with respect to the path returned by <code>getPath()</code>.

         * <p>

         * For drop modes <code>DropMode.USE_SELECTION</code> and

         * <code>DropMode.ON</code>, this index is unimportant (and it will

         * always be <code>-1</code>) as the only interesting data is the

         * path over which the drop operation occurred.

         * <p>

         * For drop mode <code>DropMode.INSERT</code>, this index

         * indicates the index at which the data should be inserted into

         * the parent path represented by <code>getPath()</code>.

         * <code>-1</code> indicates that the drop occurred over the

         * parent itself, and in most cases should be treated as inserting

         * into either the beginning or the end of the parent's list of

         * children.

         * <p>

         * For <code>DropMode.ON_OR_INSERT</code>, this value will be

         * an insert index, as described above, or <code>-1</code> if

         * the drop occurred over the path itself.

         *

         * @return the child index

         * @see #getPath

         */

        public int getChildIndex() {

            return index;

        }

        /**

         * Returns the path where dropped data should be placed in the

         * tree.

         * <p>

         * Interpretation of this value depends on the drop mode set on the

         * component. If the drop mode is <code>DropMode.USE_SELECTION</code>

         * or <code>DropMode.ON</code>, the return value is the path in the

         * tree over which the data has been (or will be) dropped.

         * <code>null</code> indicates that the drop is over empty space,

         * not associated with a particular path.

         * <p>

         * If the drop mode is <code>DropMode.INSERT</code>, the return value

         * refers to the path that should become the parent of the new data,

         * in which case <code>getChildIndex()</code> indicates where the

         * new item should be inserted into this parent path. A

         * <code>null</code> path indicates that no parent path has been

         * determined, which can happen for multiple reasons:

         * <ul>

         *    <li>The tree has no model

         *    <li>There is no root in the tree

         *    <li>The root is collapsed

         *    <li>The root is a leaf node

         * </ul>

         * It is up to the developer to decide if and how they wish to handle

         * the <code>null</code> case.

         * <p>

         * If the drop mode is <code>DropMode.ON_OR_INSERT</code>,

         * <code>getChildIndex</code> can be used to determine whether the

         * drop is on top of the path itself (<code>-1</code>) or the index

         * at which it should be inserted into the path (values other than

         * <code>-1</code>).

         *

         * @return the drop path

         * @see #getChildIndex

         */

        public TreePath getPath() {

            return path;

        }

        /**

         * Returns a string representation of this drop location.

         * This method is intended to be used for debugging purposes,

         * and the content and format of the returned string may vary

         * between implementations.

         *

         * @return a string representation of this drop location

         */

        public String toString() {

            return getClass().getName()

                   + "[dropPoint=" + getDropPoint() + ","

                   + "path=" + path + ","

                   + "childIndex=" + index + "]";

        }

    }

    /**

     * The row to expand during DnD.

     */

    private int expandRow = -1;

    private class TreeTimer extends Timer {

        public TreeTimer() {

            super(2000, null);

            setRepeats(false);

        }

        public void fireActionPerformed(ActionEvent ae) {

            JTree.this.expandRow(expandRow);

        }

    }

    /**

     * A timer to expand nodes during drop.

     */

    private TreeTimer dropTimer;

    /**

     * When <code>addTreeExpansionListener</code> is invoked,

     * and <code>settingUI</code> is true, this ivar gets set to the passed in

     * <code>Listener</code>. This listener is then notified first in

     * <code>fireTreeCollapsed</code> and <code>fireTreeExpanded</code>.

     * <p>This is an ugly workaround for a way to have the UI listener

     * get notified before other listeners.

     */

    private transient TreeExpansionListener     uiTreeExpansionListener;

    /**

     * Max number of stacks to keep around.

     */

    private static int                TEMP_STACK_SIZE = 11;

    //

    // Bound property names

    //

    /** Bound property name for <code>cellRenderer</code>. */

    public final static String        CELL_RENDERER_PROPERTY = "cellRenderer";

    /** Bound property name for <code>treeModel</code>. */

    public final static String        TREE_MODEL_PROPERTY = "model";

    /** Bound property name for <code>rootVisible</code>. */

    public final static String        ROOT_VISIBLE_PROPERTY = "rootVisible";

    /** Bound property name for <code>showsRootHandles</code>. */

    public final static String        SHOWS_ROOT_HANDLES_PROPERTY = "showsRootHandles";

    /** Bound property name for <code>rowHeight</code>. */

    public final static String        ROW_HEIGHT_PROPERTY = "rowHeight";

    /** Bound property name for <code>cellEditor</code>. */

    public final static String        CELL_EDITOR_PROPERTY = "cellEditor";

    /** Bound property name for <code>editable</code>. */

    public final static String        EDITABLE_PROPERTY = "editable";

    /** Bound property name for <code>largeModel</code>. */

    public final static String        LARGE_MODEL_PROPERTY = "largeModel";

    /** Bound property name for selectionModel. */

    public final static String        SELECTION_MODEL_PROPERTY = "selectionModel";

    /** Bound property name for <code>visibleRowCount</code>. */

    public final static String        VISIBLE_ROW_COUNT_PROPERTY = "visibleRowCount";

    /** Bound property name for <code>messagesStopCellEditing</code>. */

    public final static String        INVOKES_STOP_CELL_EDITING_PROPERTY = "invokesStopCellEditing";

    /** Bound property name for <code>scrollsOnExpand</code>. */

    public final static String        SCROLLS_ON_EXPAND_PROPERTY = "scrollsOnExpand";

    /** Bound property name for <code>toggleClickCount</code>. */

    public final static String        TOGGLE_CLICK_COUNT_PROPERTY = "toggleClickCount";

    /** Bound property name for <code>leadSelectionPath</code>.

     * @since 1.3 */

    public final static String        LEAD_SELECTION_PATH_PROPERTY = "leadSelectionPath";

    /** Bound property name for anchor selection path.

     * @since 1.3 */

    public final static String        ANCHOR_SELECTION_PATH_PROPERTY = "anchorSelectionPath";

    /** Bound property name for expands selected paths property

     * @since 1.3 */

    public final static String        EXPANDS_SELECTED_PATHS_PROPERTY = "expandsSelectedPaths";

    /**

     * Creates and returns a sample <code>TreeModel</code>.

     * Used primarily for beanbuilders to show something interesting.

     *

     * @return the default <code>TreeModel</code>

     */

    protected static TreeModel getDefaultTreeModel() {

        DefaultMutableTreeNode      root = new DefaultMutableTreeNode("JTree");

        DefaultMutableTreeNode      parent;

        parent = new DefaultMutableTreeNode("colors");

        root.add(parent);

        parent.add(new DefaultMutableTreeNode("blue"));

        parent.add(new DefaultMutableTreeNode("violet"));

        parent.add(new DefaultMutableTreeNode("red"));

        parent.add(new DefaultMutableTreeNode("yellow"));

        parent = new DefaultMutableTreeNode("sports");

        root.add(parent);

        parent.add(new DefaultMutableTreeNode("basketball"));

        parent.add(new DefaultMutableTreeNode("soccer"));

        parent.add(new DefaultMutableTreeNode("football"));

        parent.add(new DefaultMutableTreeNode("hockey"));

        parent = new DefaultMutableTreeNode("food");

        root.add(parent);

        parent.add(new DefaultMutableTreeNode("hot dogs"));

        parent.add(new DefaultMutableTreeNode("pizza"));

        parent.add(new DefaultMutableTreeNode("ravioli"));

        parent.add(new DefaultMutableTreeNode("bananas"));

        return new DefaultTreeModel(root);

    }

    /**