/*
 * Copyright (c) 1998, 2008, Oracle and/or its affiliates. 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.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package javax.swing.tree;

import javax.swing.event.TreeModelEvent;
import java.awt.Dimension;
import java.awt.Rectangle;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.NoSuchElementException;
import java.util.Stack;
import java.util.Vector;

/**
 * NOTE: This will become more open in a future release.
 * <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}.
 *
 * @author Rob Davis
 * @author Ray Ryan
 * @author Scott Violet
 */

public class VariableHeightLayoutCache extends AbstractLayoutCache {
    /**
     * The array of nodes that are currently visible, in the order they
     * are displayed.
     */
    private Vector<Object> visibleNodes;

    /**
     * This is set to true if one of the entries has an invalid size.
     */
    private boolean           updateNodeSizes;

    /**
     * The root node of the internal cache of nodes that have been shown.
     * If the treeModel is vending a network rather than a true tree,
     * there may be one cached node for each path to a modeled node.
     */
    private TreeStateNode     root;

    /**
     * Used in getting sizes for nodes to avoid creating a new Rectangle
     * every time a size is needed.
     */
    private Rectangle         boundsBuffer;

    /**
     * Maps from <code>TreePath</code> to a <code>TreeStateNode</code>.
     */
    private Hashtable<TreePath, TreeStateNode> treePathMapping;

    /**
     * A stack of stacks.
     */
    private Stack<Stack<TreePath>> tempStacks;


    public VariableHeightLayoutCache() {
        super();
        tempStacks = new Stack<Stack<TreePath>>();
        visibleNodes = new Vector<Object>();
        boundsBuffer = new Rectangle();
        treePathMapping = new Hashtable<TreePath, TreeStateNode>();
    }

    /**
     * Sets the <code>TreeModel</code> that will provide the data.
     *
     * @param newModel the <code>TreeModel</code> that is to provide the data
     * @beaninfo
     *        bound: true
     *  description: The TreeModel that will provide the data.
     */
    public void setModel(TreeModel newModel) {
        super.setModel(newModel);
        rebuild(false);
    }

    /**
     * Determines whether or not the root node from
     * the <code>TreeModel</code> is visible.
     *
     * @param rootVisible true if the root node of the tree is to be displayed
     * @see #rootVisible
     * @beaninfo
     *        bound: true
     *  description: Whether or not the root node
     *               from the TreeModel is visible.
     */
    public void setRootVisible(boolean rootVisible) {
        if(isRootVisible() != rootVisible && root != null) {
            if(rootVisible) {
                root.updatePreferredSize(0);
                visibleNodes.insertElementAt(root, 0);
            }
            else if(visibleNodes.size() > 0) {
                visibleNodes.removeElementAt(0);
                if(treeSelectionModel != null)
                    treeSelectionModel.removeSelectionPath
                        (root.getTreePath());
            }
            if(treeSelectionModel != null)
                treeSelectionModel.resetRowSelection();
            if(getRowCount() > 0)
                getNode(0).setYOrigin(0);
            updateYLocationsFrom(0);
            visibleNodesChanged();
        }
        super.setRootVisible(rootVisible);
    }

    /**
     * Sets the height of each cell.  If the specified value
     * is less than or equal to zero the current cell renderer is
     * queried for each row's height.
     *
     * @param rowHeight the height of each cell, in pixels
     * @beaninfo
     *        bound: true
     *  description: The height of each cell.
     */
    public void setRowHeight(int rowHeight) {
        if(rowHeight != getRowHeight()) {
            super.setRowHeight(rowHeight);
            invalidateSizes();
            this.visibleNodesChanged();
        }
    }

    /**
     * Sets the renderer that is responsible for drawing nodes in the tree.
     * @param nd the renderer
     */
    public void setNodeDimensions(NodeDimensions nd) {
        super.setNodeDimensions(nd);
        invalidateSizes();
        visibleNodesChanged();
    }

    /**
     * Marks the path <code>path</code> expanded state to
     * <code>isExpanded</code>.
     * @param path the <code>TreePath</code> of interest
     * @param isExpanded true if the path should be expanded, otherwise false
     */
    public void setExpandedState(TreePath path, boolean isExpanded) {
        if(path != null) {
            if(isExpanded)
                ensurePathIsExpanded(path, true);
            else {
                TreeStateNode        node = getNodeForPath(path, false, true);

                if(node != null) {
                    node.makeVisible();
                    node.collapse();
                }
            }
        }
    }

    /**
     * Returns true if the path is expanded, and visible.
     * @return true if the path is expanded and visible, otherwise false
     */
    public boolean getExpandedState(TreePath path) {
        TreeStateNode       node = getNodeForPath(path, true, false);

        return (node != null) ? (node.isVisible() && node.isExpanded()) :
                                 false;
    }

    /**
      * Returns the <code>Rectangle</code> enclosing the label portion
      * into which the item identified by <code>path</code> will be drawn.
      *
      * @param path  the path to be drawn
      * @param placeIn the bounds of the enclosing rectangle
      * @return the bounds of the enclosing rectangle or <code>null</code>
      *    if the node could not be ascertained
      */
    public Rectangle getBounds(TreePath path, Rectangle placeIn) {
        TreeStateNode       node = getNodeForPath(path, true, false);

        if(node != null) {
            if(updateNodeSizes)
                updateNodeSizes(false);
            return node.getNodeBounds(placeIn);
        }
        return null;
    }

    /**
      * Returns the path for <code>row</code>.  If <code>row</code>
      * is not visible, <code>null</code> is returned.
      *
      * @param row the location of interest
      * @return the path for <code>row</code>, or <code>null</code>
      * if <code>row</code> is not visible
      */
    public TreePath getPathForRow(int row) {
        if(row >= 0 && row < getRowCount()) {
            return getNode(row).getTreePath();
        }
        return null;
    }

    /**
      * Returns the row where the last item identified in path is visible.
      * Will return -1 if any of the elements in path are not
      * currently visible.
      *
      * @param path the <code>TreePath</code> of interest
      * @return the row where the last item in path is visible
      */
    public int getRowForPath(TreePath path) {
        if(path == null)
            return -1;

        TreeStateNode    visNode = getNodeForPath(path, true, false);

        if(visNode != null)
            return visNode.getRow();
        return -1;
    }

    /**
     * Returns the number of visible rows.
     * @return the number of visible rows
     */
    public int getRowCount() {
        return visibleNodes.size();
    }

    /**
     * Instructs the <code>LayoutCache</code> that the bounds for
     * <code>path</code> are invalid, and need to be updated.
     *
     * @param path the <code>TreePath</code> which is now invalid
     */
    public void invalidatePathBounds(TreePath path) {
        TreeStateNode       node = getNodeForPath(path, true, false);

        if(node != null) {
            node.markSizeInvalid();
            if(node.isVisible())
                updateYLocationsFrom(node.getRow());
        }
    }

    /**
     * Returns the preferred height.
     * @return the preferred height
     */
    public int getPreferredHeight() {
        // Get the height
        int           rowCount = getRowCount();

        if(rowCount > 0) {
            TreeStateNode  node = getNode(rowCount - 1);

            return node.getYOrigin() + node.getPreferredHeight();
        }
        return 0;
    }

    /**
     * Returns the preferred width and height for the region in
     * <code>visibleRegion</code>.
     *
     * @param bounds  the region being queried
     */
    public int getPreferredWidth(Rectangle bounds) {
        if(updateNodeSizes)
            updateNodeSizes(false);

        return getMaxNodeWidth();
    }

    /**
      * Returns the path to the node that is closest to x,y.  If
      * there is nothing currently visible this will return <code>null</code>,
      * otherwise it will always return a valid path.
      * If you need to test if the
      * returned object is exactly at x, y you should get the bounds for
      * the returned path and test x, y against that.
      *
      * @param x  the x-coordinate
      * @param y  the y-coordinate
      * @return the path to the node that is closest to x, y
      */
    public TreePath getPathClosestTo(int x, int y) {
        if(getRowCount() == 0)
            return null;

        if(updateNodeSizes)
            updateNodeSizes(false);

        int                row = getRowContainingYLocation(y);

        return getNode(row).getTreePath();
    }

    /**
     * Returns an <code>Enumerator</code> that increments over the visible paths
     * starting at the passed in location. The ordering of the enumeration
     * is based on how the paths are displayed.
     *
     * @param path the location in the <code>TreePath</code> to start
     * @return an <code>Enumerator</code> that increments over the visible
     *     paths
     */
    public Enumeration<TreePath> getVisiblePathsFrom(TreePath path) {
        TreeStateNode       node = getNodeForPath(path, true, false);

        if(node != null) {
            return new VisibleTreeStateNodeEnumeration(node);
        }
        return null;
    }

    /**
     * Returns the number of visible children for <code>path</code>.
     * @return the number of visible children for <code>path</code>
     */
    public int getVisibleChildCount(TreePath path) {
        TreeStateNode         node = getNodeForPath(path, true, false);

        return (node != null) ? node.getVisibleChildCount() : 0;
    }

    /**
     * Informs the <code>TreeState</code> that it needs to recalculate
     * all the sizes it is referencing.
     */
    public void invalidateSizes() {
        if(root != null)
            root.deepMarkSizeInvalid();
        if(!isFixedRowHeight() && visibleNodes.size() > 0) {
            updateNodeSizes(true);
        }
    }

    /**
      * Returns true if the value identified by <code>path</code> is
      * currently expanded.
      * @return true if the value identified by <code>path</code> is
      *    currently expanded
      */
    public boolean isExpanded(TreePath path) {
        if(path != null) {
            TreeStateNode     lastNode = getNodeForPath(path, true, false);

            return (lastNode != null && lastNode.isExpanded());
        }
        return false;
    }

    //
    // TreeModelListener methods
    //

    /**
     * Invoked after a node (or a set of siblings) has changed in some
     * way. The node(s) have not changed locations in the tree or
     * altered their children arrays, but other attributes have
     * changed and may affect presentation. Example: the name of a
     * file has changed, but it is in the same location in the file
     * system.
     *
     * <p><code>e.path</code> returns the path the parent of the
     * changed node(s).
     *
     * <p><code>e.childIndices</code> returns the index(es) of the
     * changed node(s).
     *
     * @param e the <code>TreeModelEvent</code> of interest
     */
    public void treeNodesChanged(TreeModelEvent e) {
        if(e != null) {
            int               changedIndexs[];
            TreeStateNode     changedNode;

            changedIndexs = e.getChildIndices();
            changedNode = getNodeForPath(e.getTreePath(), false, false);
            if(changedNode != null) {
                Object            changedValue = changedNode.getValue();

                /* Update the size of the changed node, as well as all the
                   child indexs that are passed in. */
                changedNode.updatePreferredSize();
                if(changedNode.hasBeenExpanded() && changedIndexs != null) {
                    int                counter;
                    TreeStateNode      changedChildNode;

                    for(counter = 0; counter < changedIndexs.length;
                        counter++) {
                        changedChildNode = (TreeStateNode)changedNode
                                    .getChildAt(changedIndexs[counter]);
                        /* Reset the user object. */
                        changedChildNode.setUserObject
                                    (treeModel.getChild(changedValue,
                                                     changedIndexs[counter]));
                        changedChildNode.updatePreferredSize();
                    }
                }
                else if (changedNode == root) {
                    // Null indicies for root indicates it changed.
                    changedNode.updatePreferredSize();
                }
                if(!isFixedRowHeight()) {
                    int          aRow = changedNode.getRow();

                    if(aRow != -1)
                        this.updateYLocationsFrom(aRow);
                }
                this.visibleNodesChanged();
            }
        }
    }


    /**
     * Invoked after nodes have been inserted into the tree.
     *
     * <p><code>e.path</code> returns the parent of the new nodes.
     * <p><code>e.childIndices</code> returns the indices of the new nodes in
     * ascending order.
     *
     * @param e the <code>TreeModelEvent</code> of interest
     */
    public void treeNodesInserted(TreeModelEvent e) {
        if(e != null) {
            int               changedIndexs[];
            TreeStateNode     changedParentNode;

            changedIndexs = e.getChildIndices();
            changedParentNode = getNodeForPath(e.getTreePath(), false, false);
            /* Only need to update the children if the node has been
               expanded once. */
            // PENDING(scott): make sure childIndexs is sorted!
            if(changedParentNode != null && changedIndexs != null &&
               changedIndexs.length > 0) {
                if(changedParentNode.hasBeenExpanded()) {
                    boolean            makeVisible;
                    int                counter;
                    Object             changedParent;
                    TreeStateNode      newNode;
                    int                oldChildCount = changedParentNode.
                                          getChildCount();

                    changedParent = changedParentNode.getValue();
                    makeVisible = ((changedParentNode == root &&
                                    !rootVisible) ||
                                   (changedParentNode.getRow() != -1 &&
                                    changedParentNode.isExpanded()));
                    for(counter = 0;counter < changedIndexs.length;counter++)
                    {
                        newNode = this.createNodeAt(changedParentNode,
                                                    changedIndexs[counter]);
                    }
                    if(oldChildCount == 0) {
                        // Update the size of the parent.
                        changedParentNode.updatePreferredSize();
                    }
                    if(treeSelectionModel != null)
                        treeSelectionModel.resetRowSelection();
                    /* Update the y origins from the index of the parent
                       to the end of the visible rows. */
                    if(!isFixedRowHeight() && (makeVisible ||
                                               (oldChildCount == 0 &&
                                        changedParentNode.isVisible()))) {
                        if(changedParentNode == root)
                            this.updateYLocationsFrom(0);
                        else
                            this.updateYLocationsFrom(changedParentNode.
                                                      getRow());
                        this.visibleNodesChanged();
                    }
                    else if(makeVisible)
                        this.visibleNodesChanged();
                }
                else if(treeModel.getChildCount(changedParentNode.getValue())
                        - changedIndexs.length == 0) {
                    changedParentNode.updatePreferredSize();
                    if(!isFixedRowHeight() && changedParentNode.isVisible())
                        updateYLocationsFrom(changedParentNode.getRow());
                }
            }
        }
    }

    /**
     * Invoked after nodes have been removed from the tree.  Note that
     * if a subtree is removed from the tree, this method may only be
     * invoked once for the root of the removed subtree, not once for
     * each individual set of siblings removed.
     *
     * <p><code>e.path</code> returns the former parent of the deleted nodes.
     *
     * <p><code>e.childIndices</code> returns the indices the nodes had
     * before they were deleted in ascending order.
     *
     * @param e the <code>TreeModelEvent</code> of interest
     */
    public void treeNodesRemoved(TreeModelEvent e) {
        if(e != null) {
            int               changedIndexs[];
            TreeStateNode     changedParentNode;

            changedIndexs = e.getChildIndices();
            changedParentNode = getNodeForPath(e.getTreePath(), false, false);
            // PENDING(scott): make sure that changedIndexs are sorted in
            // ascending order.
            if(changedParentNode != null && changedIndexs != null &&
               changedIndexs.length > 0) {
                if(changedParentNode.hasBeenExpanded()) {
                    boolean            makeInvisible;
                    int                counter;
                    int                removedRow;
                    TreeStateNode      removedNode;

                    makeInvisible = ((changedParentNode == root &&
                                      !rootVisible) ||
                                     (changedParentNode.getRow() != -1 &&
                                      changedParentNode.isExpanded()));
                    for(counter = changedIndexs.length - 1;counter >= 0;
                        counter--) {
                        removedNode = (TreeStateNode)changedParentNode.
                                getChildAt(changedIndexs[counter]);
                        if(removedNode.isExpanded()) {
                            removedNode.collapse(false);
                        }

                        /* Let the selection model now. */
                        if(makeInvisible) {
                            removedRow = removedNode.getRow();
                            if(removedRow != -1) {
                                visibleNodes.removeElementAt(removedRow);
                            }
                        }
                        changedParentNode.remove(changedIndexs[counter]);
                    }
                    if(changedParentNode.getChildCount() == 0) {
                        // Update the size of the parent.
                        changedParentNode.updatePreferredSize();
                        if (changedParentNode.isExpanded() &&
                                   changedParentNode.isLeaf()) {
                            // Node has become a leaf, collapse it.
                            changedParentNode.collapse(false);
                        }
                    }
                    if(treeSelectionModel != null)
                        treeSelectionModel.resetRowSelection();
                    /* Update the y origins from the index of the parent
                       to the end of the visible rows. */
                    if(!isFixedRowHeight() && (makeInvisible ||
                               (changedParentNode.getChildCount() == 0 &&
                                changedParentNode.isVisible()))) {
                        if(changedParentNode == root) {
                            /* It is possible for first row to have been
                               removed if the root isn't visible, in which
                               case ylocations will be off! */
                            if(getRowCount() > 0)
                                getNode(0).setYOrigin(0);
                            updateYLocationsFrom(0);
                        }
                        else
                            updateYLocationsFrom(changedParentNode.getRow());
                        this.visibleNodesChanged();
                    }
                    else if(makeInvisible)
                        this.visibleNodesChanged();
                }
                else if(treeModel.getChildCount(changedParentNode.getValue())
                        == 0) {
                    changedParentNode.updatePreferredSize();
                    if(!isFixedRowHeight() && changedParentNode.isVisible())
                        this.updateYLocationsFrom(changedParentNode.getRow());
                }
            }
        }
    }

    /**
     * Invoked after the tree has drastically changed structure from a
     * given node down.  If the path returned by <code>e.getPath</code>
     * is of length one and the first element does not identify the
     * current root node the first element should become the new root
     * of the tree.
     *
     * <p><code>e.path</code> holds the path to the node.
     * <p><code>e.childIndices</code> returns <code>null</code>.
     *
     * @param e the <code>TreeModelEvent</code> of interest
     */
    public void treeStructureChanged(TreeModelEvent e) {
        if(e != null)
        {
            TreePath          changedPath = e.getTreePath();
            TreeStateNode     changedNode;

            changedNode = getNodeForPath(changedPath, false, false);

            // Check if root has changed, either to a null root, or
            // to an entirely new root.
            if(changedNode == root ||
               (changedNode == null &&
                ((changedPath == null && treeModel != null &&
                  treeModel.getRoot() == null) ||
                 (changedPath != null && changedPath.getPathCount() == 1)))) {
                rebuild(true);
            }
            else if(changedNode != null) {
                int                              nodeIndex, oldRow;
                TreeStateNode                    newNode, parent;
                boolean                          wasExpanded, wasVisible;
                int                              newIndex;

                wasExpanded = changedNode.isExpanded();
                wasVisible = (changedNode.getRow() != -1);
                /* Remove the current node and recreate a new one. */
                parent = (TreeStateNode)changedNode.getParent();
                nodeIndex = parent.getIndex(changedNode);
                if(wasVisible && wasExpanded) {
                    changedNode.collapse(false);
                }
                if(wasVisible)
                    visibleNodes.removeElement(changedNode);
                changedNode.removeFromParent();
                createNodeAt(parent, nodeIndex);
                newNode = (TreeStateNode)parent.getChildAt(nodeIndex);
                if(wasVisible && wasExpanded)
                    newNode.expand(false);
                newIndex = newNode.getRow();
                if(!isFixedRowHeight() && wasVisible) {
                    if(newIndex == 0)
                        updateYLocationsFrom(newIndex);
                    else
                        updateYLocationsFrom(newIndex - 1);
                    this.visibleNodesChanged();
                }
                else if(wasVisible)
                    this.visibleNodesChanged();
            }
        }
    }


    //
    // Local methods
    //

    private void visibleNodesChanged() {
    }

    /**
     * Adds a mapping for node.
     */
    private void addMapping(TreeStateNode node) {
        treePathMapping.put(node.getTreePath(), node);
    }

    /**
     * Removes the mapping for a previously added node.
     */
    private void removeMapping(TreeStateNode node) {
        treePathMapping.remove(node.getTreePath());
    }

    /**
     * Returns the node previously added for <code>path</code>. This may
     * return null, if you to create a node use getNodeForPath.
     */
    private TreeStateNode getMapping(TreePath path) {
        return treePathMapping.get(path);
    }

    /**
     * Retursn the bounds for row, <code>row</code> by reference in
     * <code>placeIn</code>. If <code>placeIn</code> is null a new
     * Rectangle will be created and returned.
     */
    private Rectangle getBounds(int row, Rectangle placeIn) {
        if(updateNodeSizes)
            updateNodeSizes(false);

        if(row >= 0 && row < getRowCount()) {
            return getNode(row).getNodeBounds(placeIn);
        }
        return null;
    }

    /**
     * Completely rebuild the tree, all expanded state, and node caches are
     * removed. All nodes are collapsed, except the root.
     */
    private void rebuild(boolean clearSelection) {
        Object rootObject;

        treePathMapping.clear();
        if(treeModel != null && (rootObject = treeModel.getRoot()) != null) {
            root = createNodeForValue(rootObject);
            root.path = new TreePath(rootObject);
            addMapping(root);
            root.updatePreferredSize(0);
            visibleNodes.removeAllElements();
            if (isRootVisible())
                visibleNodes.addElement(root);
            if(!root.isExpanded())
                root.expand();
            else {
                Enumeration cursor = root.children();
                while(cursor.hasMoreElements()) {
                    visibleNodes.addElement(cursor.nextElement());
                }
                if(!isFixedRowHeight())
                    updateYLocationsFrom(0);
            }
        }
        else {
            visibleNodes.removeAllElements();
            root = null;
        }
        if(clearSelection && treeSelectionModel != null) {
            treeSelectionModel.clearSelection();
        }
        this.visibleNodesChanged();
    }

    /**
      * Creates a new node to represent the node at <I>childIndex</I> in
      * <I>parent</I>s children.  This should be called if the node doesn't
      * already exist and <I>parent</I> has been expanded at least once.
      * The newly created node will be made visible if <I>parent</I> is
      * currently expanded.  This does not update the position of any
      * cells, nor update the selection if it needs to be.  If succesful
      * in creating the new TreeStateNode, it is returned, otherwise
      * null is returned.
      */
    private TreeStateNode createNodeAt(TreeStateNode parent,
                                         int childIndex) {
        boolean                isParentRoot;
        Object                 newValue;
        TreeStateNode          newChildNode;

        newValue = treeModel.getChild(parent.getValue(), childIndex);
        newChildNode = createNodeForValue(newValue);
        parent.insert(newChildNode, childIndex);
        newChildNode.updatePreferredSize(-1);
        isParentRoot = (parent == root);
        if(newChildNode != null && parent.isExpanded() &&
           (parent.getRow() != -1 || isParentRoot)) {
            int                 newRow;

            /* Find the new row to insert this newly visible node at. */
            if(childIndex == 0) {
                if(isParentRoot && !isRootVisible())
                    newRow = 0;
                else
                    newRow = parent.getRow() + 1;
            }
            else if(childIndex == parent.getChildCount())
                newRow = parent.getLastVisibleNode().getRow() + 1;
            else {
                TreeStateNode          previousNode;

                previousNode = (TreeStateNode)parent.
                    getChildAt(childIndex - 1);
                newRow = previousNode.getLastVisibleNode().getRow() + 1;
            }
            visibleNodes.insertElementAt(newChildNode, newRow);
        }
        return newChildNode;
    }

    /**
      * Returns the TreeStateNode identified by path.  This mirrors
      * the behavior of getNodeForPath, but tries to take advantage of
      * path if it is an instance of AbstractTreePath.
      */
    private TreeStateNode getNodeForPath(TreePath path,
                                           boolean onlyIfVisible,
                                           boolean shouldCreate) {
        if(path != null) {
            TreeStateNode      node;

            node = getMapping(path);
            if(node != null) {
                if(onlyIfVisible && !node.isVisible())
                    return null;
                return node;
            }

            // Check all the parent paths, until a match is found.
            Stack<TreePath> paths;

            if(tempStacks.size() == 0) {
                paths = new Stack<TreePath>();
            }
            else {
                paths = tempStacks.pop();
            }

            try {
                paths.push(path);
                path = path.getParentPath();
                node = null;
                while(path != null) {
                    node = getMapping(path);
                    if(node != null) {
                        // Found a match, create entries for all paths in
                        // paths.
                        while(node != null && paths.size() > 0) {
                            path = paths.pop();
                            node.getLoadedChildren(shouldCreate);

                            int            childIndex = treeModel.
                                      getIndexOfChild(node.getUserObject(),
                                                  path.getLastPathComponent());

                            if(childIndex == -1 ||
                               childIndex >= node.getChildCount() ||
                               (onlyIfVisible && !node.isVisible())) {
                                node = null;
                            }
                            else
                                node = (TreeStateNode)node.getChildAt
                                               (childIndex);
                        }
                        return node;
                    }
                    paths.push(path);
                    path = path.getParentPath();
                }
            }
            finally {
                paths.removeAllElements();
                tempStacks.push(paths);
            }
            // If we get here it means they share a different root!
            // We could throw an exception...
        }
        return null;
    }

    /**
      * Updates the y locations of all of the visible nodes after
      * location.
      */
    private void updateYLocationsFrom(int location) {
        if(location >= 0 && location < getRowCount()) {
            int                    counter, maxCounter, newYOrigin;
            TreeStateNode          aNode;

            aNode = getNode(location);
            newYOrigin = aNode.getYOrigin() + aNode.getPreferredHeight();
            for(counter = location + 1, maxCounter = visibleNodes.size();
                counter < maxCounter;counter++) {
                aNode = (TreeStateNode)visibleNodes.
                    elementAt(counter);
                aNode.setYOrigin(newYOrigin);
                newYOrigin += aNode.getPreferredHeight();
            }
        }
    }

    /**
      * Resets the y origin of all the visible nodes as well as messaging
      * all the visible nodes to updatePreferredSize().  You should not
      * normally have to call this.  Expanding and contracting the nodes
      * automaticly adjusts the locations.
      * updateAll determines if updatePreferredSize() is call on all nodes
      * or just those that don't have a valid size.
      */
    private void updateNodeSizes(boolean updateAll) {
        int                      aY, counter, maxCounter;
        TreeStateNode            node;

        updateNodeSizes = false;
        for(aY = counter = 0, maxCounter = visibleNodes.size();
            counter < maxCounter; counter++) {
            node = (TreeStateNode)visibleNodes.elementAt(counter);
            node.setYOrigin(aY);
            if(updateAll || !node.hasValidSize())
                node.updatePreferredSize(counter);
            aY += node.getPreferredHeight();
        }
    }

    /**
      * Returns the index of the row containing location.  If there
      * are no rows, -1 is returned.  If location is beyond the last
      * row index, the last row index is returned.
      */
    private int getRowContainingYLocation(int location) {
        if(isFixedRowHeight()) {
            if(getRowCount() == 0)
                return -1;
            return Math.max(0, Math.min(getRowCount() - 1,
                                        location / getRowHeight()));
        }

        int                    max, maxY, mid, min, minY;
        TreeStateNode          node;

        if((max = getRowCount()) <= 0)
            return -1;
        mid = min = 0;
        while(min < max) {
            mid = (max - min) / 2 + min;
            node = (TreeStateNode)visibleNodes.elementAt(mid);
            minY = node.getYOrigin();
            maxY = minY + node.getPreferredHeight();
            if(location < minY) {
                max = mid - 1;
            }
            else if(location >= maxY) {
                min = mid + 1;
            }
            else
                break;
        }
        if(min == max) {
            mid = min;
            if(mid >= getRowCount())
                mid = getRowCount() - 1;
        }
        return mid;
    }

    /**
     * Ensures that all the path components in path are expanded, accept
     * for the last component which will only be expanded if expandLast
     * is true.
     * Returns true if succesful in finding the path.
     */
    private void ensurePathIsExpanded(TreePath aPath, boolean expandLast) {
        if(aPath != null) {
            // Make sure the last entry isn't a leaf.
            if(treeModel.isLeaf(aPath.getLastPathComponent())) {
                aPath = aPath.getParentPath();
                expandLast = true;
            }
            if(aPath != null) {
                TreeStateNode     lastNode = getNodeForPath(aPath, false,
                                                            true);

                if(lastNode != null) {
                    lastNode.makeVisible();
                    if(expandLast)
                        lastNode.expand();
                }
            }
        }
    }

    /**
     * Returns the AbstractTreeUI.VisibleNode displayed at the given row
     */
    private TreeStateNode getNode(int row) {
        return (TreeStateNode)visibleNodes.elementAt(row);
    }

    /**
      * Returns the maximum node width.
      */
    private int getMaxNodeWidth() {
        int                     maxWidth = 0;
        int                     nodeWidth;
        int                     counter;
        TreeStateNode           node;

        for(counter = getRowCount() - 1;counter >= 0;counter--) {
            node = this.getNode(counter);
            nodeWidth = node.getPreferredWidth() + node.getXOrigin();
            if(nodeWidth > maxWidth)
                maxWidth = nodeWidth;
        }
        return maxWidth;
    }

    /**
      * Responsible for creating a TreeStateNode that will be used
      * to track display information about value.
      */
    private TreeStateNode createNodeForValue(Object value) {
        return new TreeStateNode(value);
    }


    /**
     * TreeStateNode is used to keep track of each of
     * the nodes that have been expanded. This will also cache the preferred
     * size of the value it represents.
     */
    private class TreeStateNode extends DefaultMutableTreeNode {
        /** Preferred size needed to draw the user object. */
        protected int             preferredWidth;
        protected int             preferredHeight;

        /** X location that the user object will be drawn at. */
        protected int             xOrigin;

        /** Y location that the user object will be drawn at. */
        protected int             yOrigin;

        /** Is this node currently expanded? */
        protected boolean         expanded;

        /** Has this node been expanded at least once? */
        protected boolean         hasBeenExpanded;

        /** Path of this node. */
        protected TreePath        path;


        public TreeStateNode(Object value) {
            super(value);
        }

        //
        // Overriden DefaultMutableTreeNode methods
        //

        /**
         * Messaged when this node is added somewhere, resets the path
         * and adds a mapping from path to this node.
         */
        public void setParent(MutableTreeNode parent) {
            super.setParent(parent);
            if(parent != null) {
                path = ((TreeStateNode)parent).getTreePath().
                                       pathByAddingChild(getUserObject());
                addMapping(this);
            }
        }

        /**
         * Messaged when this node is removed from its parent, this messages
         * <code>removedFromMapping</code> to remove all the children.
         */
        public void remove(int childIndex) {
            TreeStateNode     node = (TreeStateNode)getChildAt(childIndex);

            node.removeFromMapping();
            super.remove(childIndex);
        }

        /**
         * Messaged to set the user object. This resets the path.
         */
        public void setUserObject(Object o) {
            super.setUserObject(o);
            if(path != null) {
                TreeStateNode      parent = (TreeStateNode)getParent();

                if(parent != null)
                    resetChildrenPaths(parent.getTreePath());
                else
                    resetChildrenPaths(null);
            }
        }

        /**
         * Returns the children of the receiver.
         * If the receiver is not currently expanded, this will return an
         * empty enumeration.
         */
        public Enumeration children() {
            if (!this.isExpanded()) {
                return DefaultMutableTreeNode.EMPTY_ENUMERATION;
            } else {
                return super.children();
            }
        }

        /**
         * Returns true if the receiver is a leaf.
         */
        public boolean isLeaf() {
            return getModel().isLeaf(this.getValue());
        }

        //
        // VariableHeightLayoutCache
        //

        /**
         * Returns the location and size of this node.
         */
        public Rectangle getNodeBounds(Rectangle placeIn) {
            if(placeIn == null)
                placeIn = new Rectangle(getXOrigin(), getYOrigin(),
                                        getPreferredWidth(),
                                        getPreferredHeight());
            else {
                placeIn.x = getXOrigin();
                placeIn.y = getYOrigin();
                placeIn.width = getPreferredWidth();
                placeIn.height = getPreferredHeight();
            }
            return placeIn;
        }

        /**
         * @return x location to draw node at.
         */
        public int getXOrigin() {
            if(!hasValidSize())
                updatePreferredSize(getRow());
            return xOrigin;
        }

        /**
         * Returns the y origin the user object will be drawn at.
         */
        public int getYOrigin() {
            if(isFixedRowHeight()) {
                int      aRow = getRow();

                if(aRow == -1)
                    return -1;
                return getRowHeight() * aRow;
            }
            return yOrigin;
        }

        /**
         * Returns the preferred height of the receiver.
         */
        public int getPreferredHeight() {
            if(isFixedRowHeight())
                return getRowHeight();
            else if(!hasValidSize())
                updatePreferredSize(getRow());
            return preferredHeight;
        }

        /**
         * Returns the preferred width of the receiver.
         */
        public int getPreferredWidth() {
            if(!hasValidSize())
                updatePreferredSize(getRow());
            return preferredWidth;
        }

        /**
         * Returns true if this node has a valid size.
         */
        public boolean hasValidSize() {
            return (preferredHeight != 0);
        }

        /**
         * Returns the row of the receiver.
         */
        public int getRow() {
            return visibleNodes.indexOf(this);
        }

        /**
         * Returns true if this node has been expanded at least once.
         */
        public boolean hasBeenExpanded() {
            return hasBeenExpanded;
        }

        /**
         * Returns true if the receiver has been expanded.
         */
        public boolean isExpanded() {
            return expanded;
        }

        /**
         * Returns the last visible node that is a child of this
         * instance.
         */
        public TreeStateNode getLastVisibleNode() {
            TreeStateNode                node = this;

            while(node.isExpanded() && node.getChildCount() > 0)
                node = (TreeStateNode)node.getLastChild();
            return node;
        }

        /**
         * Returns true if the receiver is currently visible.
         */
        public boolean isVisible() {
            if(this == root)
                return true;

            TreeStateNode        parent = (TreeStateNode)getParent();

            return (parent != null && parent.isExpanded() &&
                    parent.isVisible());
        }

        /**
         * Returns the number of children this will have. If the children
         * have not yet been loaded, this messages the model.
         */
        public int getModelChildCount() {
            if(hasBeenExpanded)
                return super.getChildCount();
            return getModel().getChildCount(getValue());
        }

        /**
         * Returns the number of visible children, that is the number of
         * children that are expanded, or leafs.
         */
        public int getVisibleChildCount() {
            int               childCount = 0;

            if(isExpanded()) {
                int         maxCounter = getChildCount();

                childCount += maxCounter;
                for(int counter = 0; counter < maxCounter; counter++)
                    childCount += ((TreeStateNode)getChildAt(counter)).
                                    getVisibleChildCount();
            }
            return childCount;
        }

        /**
         * Toggles the receiver between expanded and collapsed.
         */
        public void toggleExpanded() {
            if (isExpanded()) {
                collapse();
            } else {
                expand();
            }
        }

        /**
         * Makes the receiver visible, but invoking
         * <code>expandParentAndReceiver</code> on the superclass.
         */
        public void makeVisible() {
            TreeStateNode       parent = (TreeStateNode)getParent();

            if(parent != null)
                parent.expandParentAndReceiver();
        }

        /**
         * Expands the receiver.
         */
        public void expand() {
            expand(true);
        }

        /**
         * Collapses the receiver.
         */
        public void collapse() {
            collapse(true);
        }

        /**
         * Returns the value the receiver is representing. This is a cover
         * for getUserObject.
         */
        public Object getValue() {
            return getUserObject();
        }

        /**
         * Returns a TreePath instance for this node.
         */
        public TreePath getTreePath() {
            return path;
        }

        //
        // Local methods
        //

        /**
         * Recreates the receivers path, and all its childrens paths.
         */
        protected void resetChildrenPaths(TreePath parentPath) {
            removeMapping(this);
            if(parentPath == null)
                path = new TreePath(getUserObject());
            else
                path = parentPath.pathByAddingChild(getUserObject());
            addMapping(this);
            for(int counter = getChildCount() - 1; counter >= 0; counter--)
                ((TreeStateNode)getChildAt(counter)).resetChildrenPaths(path);
        }

        /**
         * Sets y origin the user object will be drawn at to
         * <I>newYOrigin</I>.
         */
        protected void setYOrigin(int newYOrigin) {
            yOrigin = newYOrigin;
        }

        /**
         * Shifts the y origin by <code>offset</code>.
         */
        protected void shiftYOriginBy(int offset) {
            yOrigin += offset;
        }

        /**
         * Updates the receivers preferredSize by invoking
         * <code>updatePreferredSize</code> with an argument of -1.
         */
        protected void updatePreferredSize() {
            updatePreferredSize(getRow());
        }

        /**
         * Updates the preferred size by asking the current renderer
         * for the Dimension needed to draw the user object this
         * instance represents.
         */
        protected void updatePreferredSize(int index) {
            Rectangle       bounds = getNodeDimensions(this.getUserObject(),
                                                       index, getLevel(),
                                                       isExpanded(),
                                                       boundsBuffer);

            if(bounds == null) {
                xOrigin = 0;
                preferredWidth = preferredHeight = 0;
                updateNodeSizes = true;
            }
            else if(bounds.height == 0) {
                xOrigin = 0;
                preferredWidth = preferredHeight = 0;
                updateNodeSizes = true;
            }
            else {
                xOrigin = bounds.x;
                preferredWidth = bounds.width;
                if(isFixedRowHeight())
                    preferredHeight = getRowHeight();
                else
                    preferredHeight = bounds.height;
            }
        }

        /**
         * Marks the receivers size as invalid. Next time the size, location
         * is asked for it will be obtained.
         */
        protected void markSizeInvalid() {
            preferredHeight = 0;
        }

        /**
         * Marks the receivers size, and all its descendants sizes, as invalid.
         */
        protected void deepMarkSizeInvalid() {
            markSizeInvalid();
            for(int counter = getChildCount() - 1; counter >= 0; counter--)
                ((TreeStateNode)getChildAt(counter)).deepMarkSizeInvalid();
        }

        /**
         * Returns the children of the receiver. If the children haven't
         * been loaded from the model and
         * <code>createIfNeeded</code> is true, the children are first
         * loaded.
         */
        protected Enumeration getLoadedChildren(boolean createIfNeeded) {
            if(!createIfNeeded || hasBeenExpanded)
                return super.children();

            TreeStateNode   newNode;
            Object          realNode = getValue();
            TreeModel       treeModel = getModel();
            int             count = treeModel.getChildCount(realNode);

            hasBeenExpanded = true;

            int    childRow = getRow();

            if(childRow == -1) {
                for (int i = 0; i < count; i++) {
                    newNode = createNodeForValue
                        (treeModel.getChild(realNode, i));
                    this.add(newNode);
                    newNode.updatePreferredSize(-1);
                }
            }
            else {
                childRow++;
                for (int i = 0; i < count; i++) {
                    newNode = createNodeForValue
                        (treeModel.getChild(realNode, i));
                    this.add(newNode);
                    newNode.updatePreferredSize(childRow++);
                }
            }
            return super.children();
        }

        /**
         * Messaged from expand and collapse. This is meant for subclassers
         * that may wish to do something interesting with this.
         */
        protected void didAdjustTree() {
        }

        /**
         * Invokes <code>expandParentAndReceiver</code> on the parent,
         * and expands the receiver.
         */
        protected void expandParentAndReceiver() {
            TreeStateNode       parent = (TreeStateNode)getParent();

            if(parent != null)
                parent.expandParentAndReceiver();
            expand();
        }

        /**
         * Expands this node in the tree.  This will load the children
         * from the treeModel if this node has not previously been
         * expanded.  If <I>adjustTree</I> is true the tree and selection
         * are updated accordingly.
         */
        protected void expand(boolean adjustTree) {
            if (!isExpanded() && !isLeaf()) {
                boolean         isFixed = isFixedRowHeight();
                int             startHeight = getPreferredHeight();
                int             originalRow = getRow();

                expanded = true;
                updatePreferredSize(originalRow);

                if (!hasBeenExpanded) {
                    TreeStateNode  newNode;
                    Object         realNode = getValue();
                    TreeModel      treeModel = getModel();
                    int            count = treeModel.getChildCount(realNode);

                    hasBeenExpanded = true;
                    if(originalRow == -1) {
                        for (int i = 0; i < count; i++) {
                            newNode = createNodeForValue(treeModel.getChild
                                                            (realNode, i));
                            this.add(newNode);
                            newNode.updatePreferredSize(-1);
                        }
                    }
                    else {
                        int offset = originalRow + 1;
                        for (int i = 0; i < count; i++) {
                            newNode = createNodeForValue(treeModel.getChild
                                                       (realNode, i));
                            this.add(newNode);
                            newNode.updatePreferredSize(offset);
                        }
                    }
                }

                int i = originalRow;
                Enumeration cursor = preorderEnumeration();
                cursor.nextElement(); // don't add me, I'm already in

                int newYOrigin;

                if(isFixed)
                    newYOrigin = 0;
                else if(this == root && !isRootVisible())
                    newYOrigin = 0;
                else
                    newYOrigin = getYOrigin() + this.getPreferredHeight();
                TreeStateNode   aNode;
                if(!isFixed) {
                    while (cursor.hasMoreElements()) {
                        aNode = (TreeStateNode)cursor.nextElement();
                        if(!updateNodeSizes && !aNode.hasValidSize())
                            aNode.updatePreferredSize(i + 1);
                        aNode.setYOrigin(newYOrigin);
                        newYOrigin += aNode.getPreferredHeight();
                        visibleNodes.insertElementAt(aNode, ++i);
                    }
                }
                else {
                    while (cursor.hasMoreElements()) {
                        aNode = (TreeStateNode)cursor.nextElement();
                        visibleNodes.insertElementAt(aNode, ++i);
                    }
                }

                if(adjustTree && (originalRow != i ||
                                  getPreferredHeight() != startHeight)) {
                    // Adjust the Y origin of any nodes following this row.
                    if(!isFixed && ++i < getRowCount()) {
                        int              counter;
                        int              heightDiff = newYOrigin -
                            (getYOrigin() + getPreferredHeight()) +
                            (getPreferredHeight() - startHeight);

                        for(counter = visibleNodes.size() - 1;counter >= i;
                            counter--)
                            ((TreeStateNode)visibleNodes.elementAt(counter)).
                                shiftYOriginBy(heightDiff);
                    }
                    didAdjustTree();
                    visibleNodesChanged();
                }

                // Update the rows in the selection
                if(treeSelectionModel != null) {
                    treeSelectionModel.resetRowSelection();
                }
            }
        }

        /**
         * Collapses this node in the tree.  If <I>adjustTree</I> is
         * true the tree and selection are updated accordingly.
         */
        protected void collapse(boolean adjustTree) {
            if (isExpanded()) {
                Enumeration cursor = preorderEnumeration();
                cursor.nextElement(); // don't remove me, I'm still visible
                int rowsDeleted = 0;
                boolean isFixed = isFixedRowHeight();
                int lastYEnd;
                if(isFixed)
                    lastYEnd = 0;
                else
                    lastYEnd = getPreferredHeight() + getYOrigin();
                int startHeight = getPreferredHeight();
                int startYEnd = lastYEnd;
                int myRow = getRow();

                if(!isFixed) {
                    while(cursor.hasMoreElements()) {
                        TreeStateNode node = (TreeStateNode)cursor.
                            nextElement();
                        if (node.isVisible()) {
                            rowsDeleted++;
                            //visibleNodes.removeElement(node);
                            lastYEnd = node.getYOrigin() +
                                node.getPreferredHeight();
                        }
                    }
                }
                else {
                    while(cursor.hasMoreElements()) {
                        TreeStateNode node = (TreeStateNode)cursor.
                            nextElement();
                        if (node.isVisible()) {
                            rowsDeleted++;
                            //visibleNodes.removeElement(node);
                        }
                    }
                }

                // Clean up the visible nodes.
                for (int counter = rowsDeleted + myRow; counter > myRow;
                     counter--) {
                    visibleNodes.removeElementAt(counter);
                }

                expanded = false;

                if(myRow == -1)
                    markSizeInvalid();
                else if (adjustTree)
                    updatePreferredSize(myRow);

                if(myRow != -1 && adjustTree &&
                   (rowsDeleted > 0 || startHeight != getPreferredHeight())) {
                    // Adjust the Y origin of any rows following this one.
                    startYEnd += (getPreferredHeight() - startHeight);
                    if(!isFixed && (myRow + 1) < getRowCount() &&
                       startYEnd != lastYEnd) {
                        int                 counter, maxCounter, shiftAmount;

                        shiftAmount = startYEnd - lastYEnd;
                        for(counter = myRow + 1, maxCounter =
                                visibleNodes.size();
                            counter < maxCounter;counter++)
                            ((TreeStateNode)visibleNodes.elementAt(counter))
                                .shiftYOriginBy(shiftAmount);
                    }
                    didAdjustTree();
                    visibleNodesChanged();
                }
                if(treeSelectionModel != null && rowsDeleted > 0 &&
                   myRow != -1) {
                    treeSelectionModel.resetRowSelection();
                }
            }
        }

        /**
         * Removes the receiver, and all its children, from the mapping
         * table.
         */
        protected void removeFromMapping() {
            if(path != null) {
                removeMapping(this);
                for(int counter = getChildCount() - 1; counter >= 0; counter--)
                    ((TreeStateNode)getChildAt(counter)).removeFromMapping();
            }
        }
    } // End of VariableHeightLayoutCache.TreeStateNode


    /**
     * An enumerator to iterate through visible nodes.
     */
    private class VisibleTreeStateNodeEnumeration implements
                     Enumeration<TreePath> {
        /** Parent thats children are being enumerated. */
        protected TreeStateNode       parent;
        /** Index of next child. An index of -1 signifies parent should be
         * visibled next. */
        protected int                 nextIndex;
        /** Number of children in parent. */
        protected int                 childCount;

        protected VisibleTreeStateNodeEnumeration(TreeStateNode node) {
            this(node, -1);
        }

        protected VisibleTreeStateNodeEnumeration(TreeStateNode parent,
                                                  int startIndex) {
            this.parent = parent;
            this.nextIndex = startIndex;
            this.childCount = this.parent.getChildCount();
        }

        /**
         * @return true if more visible nodes.
         */
        public boolean hasMoreElements() {
            return (parent != null);
        }

        /**
         * @return next visible TreePath.
         */
        public TreePath nextElement() {
            if(!hasMoreElements())
                throw new NoSuchElementException("No more visible paths");

            TreePath                retObject;

            if(nextIndex == -1) {
                retObject = parent.getTreePath();
            }
            else {
                TreeStateNode   node = (TreeStateNode)parent.
                                        getChildAt(nextIndex);

                retObject = node.getTreePath();
            }
            updateNextObject();
            return retObject;
        }

        /**
         * Determines the next object by invoking <code>updateNextIndex</code>
         * and if not succesful <code>findNextValidParent</code>.
         */
        protected void updateNextObject() {
            if(!updateNextIndex()) {
                findNextValidParent();
            }
        }

        /**
         * Finds the next valid parent, this should be called when nextIndex
         * is beyond the number of children of the current parent.
         */
        protected boolean findNextValidParent() {
            if(parent == root) {
                // mark as invalid!
                parent = null;
                return false;
            }
            while(parent != null) {
                TreeStateNode      newParent = (TreeStateNode)parent.
                                                  getParent();

                if(newParent != null) {
                    nextIndex = newParent.getIndex(parent);
                    parent = newParent;
                    childCount = parent.getChildCount();
                    if(updateNextIndex())
                        return true;
                }
                else
                    parent = null;
            }
            return false;
        }

        /**
         * Updates <code>nextIndex</code> returning false if it is beyond
         * the number of children of parent.
         */
        protected boolean updateNextIndex() {
            // nextIndex == -1 identifies receiver, make sure is expanded
            // before descend.
            if(nextIndex == -1 && !parent.isExpanded())
                return false;

            // Check that it can have kids
            if(childCount == 0)
                return false;
            // Make sure next index not beyond child count.
            else if(++nextIndex >= childCount)
                return false;

            TreeStateNode       child = (TreeStateNode)parent.
                                        getChildAt(nextIndex);

            if(child != null && child.isExpanded()) {
                parent = child;
                nextIndex = -1;
                childCount = child.getChildCount();
            }
            return true;
        }
    } // VariableHeightLayoutCache.VisibleTreeStateNodeEnumeration
}