//import java.beans.Transient;
import java.io.*;
import java.util.*;

/**
 * A MyTreeNode is a general-purpose node in a tree data structure.
 * For examples of using default mutable tree nodes, see
 * https://docs.oracle.com/javase/tutorial/uiswing/components/tree.html
 * in The Java Tutorial.
 *
 * A tree node may have at most one parent and 0 or more children.
 * MyTreeNode 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.
 *
 * This class provides enumerations for efficiently traversing a tree
 * or subtree in various orders or for following the path between two
 * nodes. A MyTreeNode may also hold a reference to a user object, the
 * use of which is left to the user. Asking a MyTreeNode for its
 * string representation with toString() returns the string
 * representation of its user object.
 *
 * This is not a thread safe class. If you intend to use a MyTreeNode
 * (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.
 *
 * While MyTreeNode implements the MutableTreeNode interface and will
 * allow you to add in any implementation of MutableTreeNode not all
 * of the methods in MyTreeNode will be applicable to all
 * MutableTreeNodes implementations. Especially with some of the
 * enumerations that are provided, using some of these methods assumes
 * the MyTreeNode contains only DefaultMutableNode instances. All of
 * the TreeNode/MutableTreeNode methods will behave as defined no
 * matter what implementations are added.
 */
public class MyTreeNode {

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

  /** array of children, may be null if this node has no children */
  protected ArrayList<MyTreeNode> 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 MyTreeNode() {
    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 MyTreeNode(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 MyTreeNode(Object userObject, boolean allowsChildren) {
    super();
    parent = null;
    this.allowsChildren = allowsChildren;
    this.userObject = userObject;
  }


  //
  //  Primitives
  //

  /**
   * Removes newChild 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 childIndex. newChild 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
   *                          childIndex is out of bounds
   * @exception       IllegalArgumentException        if
   *                          newChild is null or is an
   *                          ancestor of this node
   * @exception       IllegalStateException   if this node does not allow
   *                                          children
   */
  public void insert(MyTreeNode 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");
    }

    MyTreeNode oldParent = newChild.getParent();

    if(oldParent != null) {
      oldParent.remove(newChild);
    }
    newChild.setParent(this);
    if(children == null) {
      children = new ArrayList<MyTreeNode>();
    }
    children.add(childIndex, newChild);
  }

  /**
   * 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 MutableTreeNode.
   *
   * @param   childIndex      the index in this node's child array
   *                          of the child to remove
   * @exception       ArrayIndexOutOfBoundsException  if
   *                          childIndex is out of bounds
   */
  public void remove(int childIndex) {
    MyTreeNode child = getChildAt(childIndex);
    children.remove(childIndex);
    child.setParent(null);
  }

  /**
   * Sets this node's parent to newParent but does not change the
   * parent's child array. This method is called from insert() and
   * remove() to reassign a child's parent, it should not be messaged
   * from anywhere else.
   *
   * @param   newParent       this node's new parent
   */
  public void setParent(MyTreeNode 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 MyTreeNode 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 index
   *                                          is out of bounds
   * @return  the TreeNode in this node's child array at  the specified index
   */
  public MyTreeNode getChildAt(int index) {
    if(children == null) {
      throw new ArrayIndexOutOfBoundsException("node has no children");
    }
    return children.get(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 -1. 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 aChild
   *                                                  is null
   * @return  an int giving the index of the node in this node's child
   *          array, or -1 if the specified node is a not
   *          a child of this node
   */
  public int getIndex(MyTreeNode aChild) {
    if(aChild == null) {
      throw new IllegalArgumentException("argument is null");
    }

    if(!isNodeChild(aChild)) {
      return -1;
    }
    return children.indexOf(aChild);        // linear search
  }

  /**
   * 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 userObject.
   *
   * @param   userObject      the Object that constitutes this node's
   *                          user-specified data
   */
  public void setUserObject(Object userObject) {
    this.userObject = userObject;
  }

  /**
   * Returns this node's user object.
   *
   * @return  the Object stored at this node by the user
   */
  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() {
    MyTreeNode parent = getParent();
    if(parent != null) {
      parent.remove(this);
    }
  }

  /**
   * Removes aChild from this node's child array, giving it a
   * null parent.
   *
   * @param   aChild  a child of this node to remove
   * @exception       IllegalArgumentException        if aChild
   *                                  is null or is not a child of this node
   */
  public void remove(MyTreeNode 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 newChild from its parent and makes it a child of this
   * node by adding it to the end of this node's child array.
   *
   * @param   newChild        node to add as a child of this node
   * @exception       IllegalArgumentException    if newChild
   *                                          is null
   * @exception       IllegalStateException   if this node does not allow
   *                                          children
   */
  public void add(MyTreeNode newChild) {
    if(newChild != null && newChild.getParent() == this)
      insert(newChild, getChildCount() - 1);
    else
      insert(newChild, getChildCount());
  }



  //
  //  Tree Queries
  //

  /**
   * Returns true if anotherNode 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 anotherNode is null, this method returns false. This operation
   * is at worst O(h) where h is the distance from the root to this
   * node.
   *
   * @param   anotherNode     node to test as an ancestor of this node
   * @return  true if this node is a descendant of anotherNode
   */
  public boolean isNodeAncestor(MyTreeNode anotherNode) {
    if(anotherNode == null) {
      return false;
    }

    MyTreeNode ancestor = this;

    do {
      if(ancestor == anotherNode) {
        return true;
      }
    } while((ancestor = ancestor.getParent()) != null);

    return false;
  }

  /**
   * Returns the path from the root, to get to this node. The last
   * element in the path is this node.
   *
   * @return an array of TreeNode objects giving the path, where the
   *         first element in the path is the root and the last
   *         element is this node.
   */
  public MyTreeNode[] getPath() {
    return getPathToRoot(this, 0);
  }

  /**
   * Builds the parents of node up to and including the root node,
   * where the original node is the last element in the returned
   * array. The length of the returned array gives the node's depth in
   * the tree.
   *
   * @param aNode  the TreeNode to get the path for
   * @param depth  an int giving the number of steps already taken towards
   *        the root (on recursive calls), used to size the returned array
   * @return an array of TreeNodes giving the path from the root to the
   *         specified node
   */
  protected MyTreeNode[] getPathToRoot(MyTreeNode aNode, int depth) {
    MyTreeNode[] retNodes;

    /* Check for null, in case someone passed in a null node, or
       they passed in an element that isn't rooted at root. */
    if(aNode == null) {
      if(depth == 0)
        return null;
      else
        retNodes = new MyTreeNode[depth];
    }
    else {
      depth++;
      retNodes = getPathToRoot(aNode.getParent(), depth);
      retNodes[retNodes.length - depth] = aNode;
    }
    return retNodes;
  }

  /**
   * Returns the user object path, from the root, to get to this node.
   * If some of the TreeNodes in the path have null user objects, the
   * returned path will contain nulls.
   */
  public Object[] getUserObjectPath() {
    MyTreeNode[] realPath = getPath();
    Object[] retPath = new Object[realPath.length];

    for(int counter = 0; counter < realPath.length; counter++)
      retPath[counter] = realPath[counter].getUserObject();
    return retPath;
  }

  /**
   * Returns the root of the tree that contains this node. The root is
   * the ancestor with a null parent.
   *
   * @return  the root of the tree that contains this node
   */
  public MyTreeNode getRoot() {
    MyTreeNode ancestor = this;
    MyTreeNode previous;

    do {
      previous = ancestor;
      ancestor = ancestor.getParent();
    } while(ancestor != null);

    return previous;
  }


  /**
   * Returns true if this node is the root of the tree. The root is
   * the only node in the tree with a null parent; every tree has
   * exactly one root.
   *
   * @return  true if this node is the root of its tree
   */
  public boolean isRoot() {
    return getParent() == null;
  }

  //
  //  Child Queries
  //

  /**
   * Returns true if aNode is a child of this node. If aNode is null,
   * this method returns false.
   *
   * @return  true if aNode is a child of this node; false if
   *                  aNode is null
   */
  public boolean isNodeChild(MyTreeNode aNode) {
    boolean retval;

    if(aNode == null) {
      retval = false;
    } else {
      if(getChildCount() == 0) {
        retval = false;
      } else {
        retval = (aNode.getParent() == this);
      }
    }

    return retval;
  }

  /**
   * Returns true if this node has no children. To distinguish between
   * nodes that have no children and nodes that cannot have children
   * (e.g. to distinguish files from empty directories), use this
   * method in conjunction with getAllowsChildren
   *
   * @return  true if this node has no children
   */
  public boolean isLeaf() {
    return (getChildCount() == 0);
  }

  /**
   * Returns the result of sending toString() to this node's user
   * object, or the empty string if the node has no user object.
   */
  public String toString() {
    if(userObject == null) {
      return "";
    } else {
      return userObject.toString();
    }
  }
} // End of class MyTreeNode