package Tree;

import java.util.List;

/**
 * This class implements a tree data type. Operations must follow the specified
 * comments exactly. You may not add new public methods, nor modify the name,
 * parameters, or return types of the methods provided. You may, and are highly
 * encouraged to write new classes, protected/private methods.
 * 
 * The TreeNode parameter passed into the various methods must always uniquely
 * identify a node or location in the tree.
 * 
 * @author 
 * 
 */
public class TreeStructure {
    /**
     * Creates a new tree with a root. This method must initialize the root such
     * that getRoot() does not return null. Furthermore, the parent of the root
     * should be the root itself.
     */
    public TreeStructure() {
    }

    /**
     * Returns the key for a node.
     * 
     * @param n
     *            the node
     * @return the key of the node.
     */
    public String getKey(TreeNode n) {
	return null;
    }

    /**
     * Returns the value of a node.
     * 
     * @param n
     *            the node
     * @return the value of the node
     */
    public String getValue(TreeNode n) {
	return null;
    }

    /**
     * Returns the node's parent. Mutating the returned value should not change
     * the TreeStructure in any way. This method should run in O(1).
     * 
     * @param currentNode
     *            the node whose parent(s) is/are required
     * 
     * @return the node's parent
     */
    public TreeNode getParent(TreeNode currentNode) {
	return null;
    }

    /**
     * Return the TreeStructure's root
     * 
     * @return the root
     */
    public TreeNode getRoot() {
	return null;
    }

    /**
     * Creates and returns a TreeNode object. TreeNodes should not be mutable
     * outside of the package.
     * 
     * @param key
     *            the key of the data the node holds
     * 
     * @param value
     *            the data the node holds
     * 
     * @return the node if successful, null otherwise.
     */
    public TreeNode makeNode(String key, String value) {
	return null;
    }

    /**
     * Adds node to specified location. The node to be added may contain
     * children which should be added to the tree preserving their original
     * structure.
     * 
     * If toAdd is already in the tree, then the adding is performed as if toAdd
     * and all its descendants were first copied/cloned, then the contents of
     * the copy are added as descendants of the specified parent.
     * 
     * This method should run in O(1) for adding a node not already in the tree,
     * and O(d) for adding a node already in the tree, where d is the number of
     * descendants of toAdd.
     * 
     * @param toAdd
     *            node to be added
     * @param parent
     *            the parent of the node being added (specifies location to add)
     * @return true if successful, false otherwise
     * 
     */
    public boolean addNode(TreeNode toAdd, TreeNode parent) {
	return false;
    }

    /**
     * Acts exactly as AddNode does, but also changes the key of the added node
     * to newKey.
     * 
     * If the argument toAdd is already in the tree, a deep copy is performed.   
     * The method changes the key of the new node, not of the original  
     * argument toAdd. If the argument toAdd is not in the tree, it 
     * changes the name of toAdd.
     * 
     * @param toAdd
     *            node to be added
     * @param parent
     *            the parent of the node being added (specifies location to add)
     * @param newKey
     *            The new key of the node.
     * @return true if successful, false otherwise
     */
    public boolean addNode(TreeNode toAdd, TreeNode parent, String newKey) {
	return false;

    }

    /**
     * Removes node at the current location. This method should preserve all
     * children of the node to be removed, such that if the node is added back
     * to the tree using AddNode, all the original children of the node should
     * be added with it. This method should run in O(1) time, regardless of the
     * number or depth of descendants that it has.
     * 
     * @param node
     *            node to be removed. No modifications to the tree structure is
     *            to be possible using only this node without calling
     *            TreeStructure methods.
     * 
     * @return the removed node if successful, null otherwise.
     */
    public TreeNode removeNode(TreeNode node) {
	return null;
    }

    /**
     * Returns a list of the node's children. Ensure that mutating this list
     * should not mutate the structure of the tree in any way.
     * 
     * This method should run in O(1).
     * 
     * @param currentNode
     *            the node whose children are required
     * 
     * @return A List<TreeNode> of the node's children. No modifications to the
     *         tree structure is possible using only this list without calling
     *         other TreeStructure methods. If the node has no children, it
     *         should return an empty list. The ordering of this list is
     *         arbitrary.
     */
    public List<TreeNode> getChild(TreeNode currentNode) {
	return null;
    }


}