/*

 * Copyright (c) 1997, 2014, 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;

   // ISSUE: this class depends on nothing in AWT -- move to java.util?

import java.beans.Transient;

import java.io.*;

import java.util.*;

/**

 * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data

 * structure.

 * For examples of using default mutable tree nodes, see

 * <a

 href="http://docs.oracle.com/javase/tutorial/uiswing/components/tree.html">How to Use Trees</a>

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

 *

 * <p>

 *

 * A tree node may have at most one parent and 0 or more children.

 * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a

 * node's parent and children and also operations for examining the tree that

 * the node is a part of.  A node's tree is the set of all nodes that can be

 * reached by starting at the node and following all the possible links to

 * parents and children.  A node with no parent is the root of its tree; a

 * node with no children is a leaf.  A tree may consist of many subtrees,

 * each node acting as the root for its own subtree.

 * <p>

 * This class provides enumerations for efficiently traversing a tree or

 * subtree in various orders or for following the path between two nodes.

 * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the

 * use of which is left to the user.  Asking a <code>DefaultMutableTreeNode</code> for its

 * string representation with <code>toString()</code> returns the string

 * representation of its user object.

 * <p>

 * <b>This is not a thread safe class.</b>If you intend to use

 * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you

 * need to do your own synchronizing. A good convention to adopt is

 * synchronizing on the root node of a tree.

 * <p>

 * While DefaultMutableTreeNode implements the MutableTreeNode interface and

 * will allow you to add in any implementation of MutableTreeNode not all

 * of the methods in DefaultMutableTreeNode will be applicable to all

 * MutableTreeNodes implementations. Especially with some of the enumerations

 * that are provided, using some of these methods assumes the

 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All

 * of the TreeNode/MutableTreeNode methods will behave as defined no

 * matter what implementations are added.

 *

 * <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™

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

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

 *

 * @see MutableTreeNode

 *

 * @author Rob Davis

 */

@SuppressWarnings("serial") // Same-version serialization only

public class DefaultMutableTreeNode implements Cloneable,

       MutableTreeNode, Serializable

{

    private static final long serialVersionUID = -4298474751201349152L;

    /**

     * An enumeration that is always empty. This is used when an enumeration

     * of a leaf node's children is requested.

     */

    static public final Enumeration<TreeNode> EMPTY_ENUMERATION

        = Collections.emptyEnumeration();

    /** this node's parent, or null if this node has no parent */

    protected MutableTreeNode   parent;

    /** array of children, may be null if this node has no children */

    protected Vector<TreeNode> children;

    /** optional user object */

    transient protected Object  userObject;

    /** true if the node is able to have children */

    protected boolean           allowsChildren;

    /**

     * Creates a tree node that has no parent and no children, but which

     * allows children.

     */

    public DefaultMutableTreeNode() {

        this(null);

    }

    /**

     * Creates a tree node with no parent, no children, but which allows

     * children, and initializes it with the specified user object.

     *

     * @param userObject an Object provided by the user that constitutes

     *                   the node's data

     */

    public DefaultMutableTreeNode(Object userObject) {

        this(userObject, true);

    }

    /**

     * Creates a tree node with no parent, no children, initialized with

     * the specified user object, and that allows children only if

     * specified.

     *

     * @param userObject an Object provided by the user that constitutes

     *        the node's data

     * @param allowsChildren if true, the node is allowed to have child

     *        nodes -- otherwise, it is always a leaf node

     */

    public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) {

        super();

        parent = null;

        this.allowsChildren = allowsChildren;

        this.userObject = userObject;

    }

    //

    //  Primitives

    //

    /**

     * Removes <code>newChild</code> from its present parent (if it has a

     * parent), sets the child's parent to this node, and then adds the child

     * to this node's child array at index <code>childIndex</code>.

     * <code>newChild</code> must not be null and must not be an ancestor of

     * this node.

     *

     * @param   newChild        the MutableTreeNode to insert under this node

     * @param   childIndex      the index in this node's child array

     *                          where this node is to be inserted

     * @exception       ArrayIndexOutOfBoundsException  if

     *                          <code>childIndex</code> is out of bounds

     * @exception       IllegalArgumentException        if

     *                          <code>newChild</code> is null or is an

     *                          ancestor of this node

     * @exception       IllegalStateException   if this node does not allow

     *                                          children

     * @see     #isNodeDescendant

     */

    public void insert(MutableTreeNode newChild, int childIndex) {

        if (!allowsChildren) {

            throw new IllegalStateException("node does not allow children");

        } else if (newChild == null) {

            throw new IllegalArgumentException("new child is null");

        } else if (isNodeAncestor(newChild)) {

            throw new IllegalArgumentException("new child is an ancestor");

        }

            MutableTreeNode oldParent = (MutableTreeNode)newChild.getParent();

            if (oldParent != null) {

                oldParent.remove(newChild);

            }

            newChild.setParent(this);

            if (children == null) {

                children = new Vector<>();

            }

            children.insertElementAt(newChild, childIndex);

    }

    /**

     * Removes the child at the specified index from this node's children

     * and sets that node's parent to null. The child node to remove

     * must be a <code>MutableTreeNode</code>.

     *

     * @param   childIndex      the index in this node's child array

     *                          of the child to remove

     * @exception       ArrayIndexOutOfBoundsException  if

     *                          <code>childIndex</code> is out of bounds

     */

    public void remove(int childIndex) {

        MutableTreeNode child = (MutableTreeNode)getChildAt(childIndex);

        children.removeElementAt(childIndex);

        child.setParent(null);

    }

    /**

     * Sets this node's parent to <code>newParent</code> but does not

     * change the parent's child array.  This method is called from

     * <code>insert()</code> and <code>remove()</code> to

     * reassign a child's parent, it should not be messaged from anywhere

     * else.

     *

     * @param   newParent       this node's new parent

     */

    @Transient

    public void setParent(MutableTreeNode newParent) {

        parent = newParent;

    }

    /**

     * Returns this node's parent or null if this node has no parent.

     *

     * @return  this node's parent TreeNode, or null if this node has no parent

     */

    public TreeNode getParent() {

        return parent;

    }

    /**

     * Returns the child at the specified index in this node's child array.

     *

     * @param   index   an index into this node's child array

     * @exception       ArrayIndexOutOfBoundsException  if <code>index</code>

     *                                          is out of bounds

     * @return  the TreeNode in this node's child array at  the specified index

     */

    public TreeNode getChildAt(int index) {

        if (children == null) {

            throw new ArrayIndexOutOfBoundsException("node has no children");

        }

        return children.elementAt(index);

    }

    /**

     * Returns the number of children of this node.

     *

     * @return  an int giving the number of children of this node

     */

    public int getChildCount() {

        if (children == null) {

            return 0;

        } else {

            return children.size();

        }

    }

    /**

     * Returns the index of the specified child in this node's child array.

     * If the specified node is not a child of this node, returns

     * <code>-1</code>.  This method performs a linear search and is O(n)

     * where n is the number of children.

     *

     * @param   aChild  the TreeNode to search for among this node's children

     * @exception       IllegalArgumentException        if <code>aChild</code>

     *                                                  is null

     * @return  an int giving the index of the node in this node's child

     *          array, or <code>-1</code> if the specified node is a not

     *          a child of this node

     */

    public int getIndex(TreeNode aChild) {

        if (aChild == null) {

            throw new IllegalArgumentException("argument is null");

        }

        if (!isNodeChild(aChild)) {

            return -1;

        }

        return children.indexOf(aChild);        // linear search

    }

    /**

     * Creates and returns a forward-order enumeration of this node's

     * children.  Modifying this node's child array invalidates any child

     * enumerations created before the modification.

     *

     * @return  an Enumeration of this node's children

     */

    public Enumeration<TreeNode> children() {

        if (children == null) {

            return EMPTY_ENUMERATION;

        } else {

            return children.elements();

        }

    }

    /**

     * Determines whether or not this node is allowed to have children.

     * If <code>allows</code> is false, all of this node's children are

     * removed.

     * <p>

     * Note: By default, a node allows children.

     *

     * @param   allows  true if this node is allowed to have children

     */

    public void setAllowsChildren(boolean allows) {

        if (allows != allowsChildren) {

            allowsChildren = allows;

            if (!allowsChildren) {

                removeAllChildren();

            }

        }

    }

    /**

     * Returns true if this node is allowed to have children.

     *

     * @return  true if this node allows children, else false

     */

    public boolean getAllowsChildren() {

        return allowsChildren;

    }

    /**

     * Sets the user object for this node to <code>userObject</code>.

     *

     * @param   userObject      the Object that constitutes this node's

     *                          user-specified data

     * @see     #getUserObject

     * @see     #toString

     */

    public void setUserObject(Object userObject) {

        this.userObject = userObject;

    }

    /**

     * Returns this node's user object.

     *

     * @return  the Object stored at this node by the user

     * @see     #setUserObject

     * @see     #toString

     */

    public Object getUserObject() {

        return userObject;

    }

    //

    //  Derived methods

    //

    /**

     * Removes the subtree rooted at this node from the tree, giving this

     * node a null parent.  Does nothing if this node is the root of its

     * tree.

     */

    public void removeFromParent() {

        MutableTreeNode parent = (MutableTreeNode)getParent();

        if (parent != null) {

            parent.remove(this);

        }

    }

    /**

     * Removes <code>aChild</code> from this node's child array, giving it a

     * null parent.

     *

     * @param   aChild  a child of this node to remove

     * @exception       IllegalArgumentException        if <code>aChild</code>

     *                                  is null or is not a child of this node

     */

    public void remove(MutableTreeNode aChild) {

        if (aChild == null) {

            throw new IllegalArgumentException("argument is null");

        }

        if (!isNodeChild(aChild)) {

            throw new IllegalArgumentException("argument is not a child");

        }

        remove(getIndex(aChild));       // linear search

    }

    /**

     * Removes all of this node's children, setting their parents to null.

     * If this node has no children, this method does nothing.

     */

    public void removeAllChildren() {

        for (int i = getChildCount()-1; i >= 0; i--) {

            remove(i);

        }

    }

    /**

     * Removes <code>newChild</code> from its parent and makes it a child of

     * this node by adding it to the end of this node's child array.

     *

     * @see             #insert

     * @param   newChild        node to add as a child of this node

     * @exception       IllegalArgumentException    if <code>newChild</code>

     *                                          is null

     * @exception       IllegalStateException   if this node does not allow

     *                                          children

     */

    public void add(MutableTreeNode newChild) {

        if(newChild != null && newChild.getParent() == this)

            insert(newChild, getChildCount() - 1);

        else

            insert(newChild, getChildCount());

    }

    //

    //  Tree Queries

    //

    /**

     * Returns true if <code>anotherNode</code> is an ancestor of this node

     * -- if it is this node, this node's parent, or an ancestor of this

     * node's parent.  (Note that a node is considered an ancestor of itself.)

     * If <code>anotherNode</code> is null, this method returns false.  This

     * operation is at worst O(h) where h is the distance from the root to

     * this node.

     *

     * @see             #isNodeDescendant

     * @see             #getSharedAncestor

     * @param   anotherNode     node to test as an ancestor of this node

     * @return  true if this node is a descendant of <code>anotherNode</code>

     */

    public boolean isNodeAncestor(TreeNode anotherNode) {

        if (anotherNode == null) {

            return false;

        }

        TreeNode ancestor = this;

        do {

            if (ancestor == anotherNode) {

                return true;

            }

        } while((ancestor = ancestor.getParent()) != null);

        return false;

    }

    /**

     * Returns true if <code>anotherNode</code> is a descendant of this node

     * -- if it is this node, one of this node's children, or a descendant of

     * one of this node's children.  Note that a node is considered a

     * descendant of itself.  If <code>anotherNode</code> is null, returns

     * false.  This operation is at worst O(h) where h is the distance from the

     * root to <code>anotherNode</code>.

     *

     * @see     #isNodeAncestor

     * @see     #getSharedAncestor

     * @param   anotherNode     node to test as descendant of this node

     * @return  true if this node is an ancestor of <code>anotherNode</code>

     */

    public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {

        if (anotherNode == null)

            return false;

        return anotherNode.isNodeAncestor(this);

    }

    /**

     * Returns the nearest common ancestor to this node and <code>aNode</code>.

     * Returns null, if no such ancestor exists -- if this node and

     * <code>aNode</code> are in different trees or if <code>aNode</code> is

     * null.  A node is considered an ancestor of itself.

     *

     * @see     #isNodeAncestor

     * @see     #isNodeDescendant

     * @param   aNode   node to find common ancestor with

     * @return  nearest ancestor common to this node and <code>aNode</code>,

     *          or null if none

     */

    public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {

        if (aNode == this) {

            return this;

        } else if (aNode == null) {

            return null;

        }

        int             level1, level2, diff;

        TreeNode        node1, node2;

        level1 = getLevel();

        level2 = aNode.getLevel();

        if (level2 > level1) {

            diff = level2 - level1;

            node1 = aNode;

            node2 = this;

        } else {

            diff = level1 - level2;

            node1 = this;

            node2 = aNode;

        }

        // Go up the tree until the nodes are at the same level

        while (diff > 0) {

            node1 = node1.getParent();

            diff--;

        }

        // Move up the tree until we find a common ancestor.  Since we know

        // that both nodes are at the same level, we won't cross paths

        // unknowingly (if there is a common ancestor, both nodes hit it in

        // the same iteration).

        do {

            if (node1 == node2) {

                return node1;

            }

            node1 = node1.getParent();

            node2 = node2.getParent();

        } while (node1 != null);// only need to check one -- they're at the

        // same level so if one is null, the other is

        if (node1 != null || node2 != null) {